买卖股票的最佳时机「变题」

变题一：交易一次

题目详情可见 买卖股票的最佳时机

x
public int maxProfit(int[] prices) {
    int n = prices.length;
    int[][] dp = new int[n + 1][2];
    dp[0][1] = Integer.MIN_VALUE;
    for (int i = 1; i <= n; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1]);
        dp[i][1] = Math.max(dp[i - 1][1], -prices[i - 1]);
    }
    return dp[n][0];
}
// 空间优化
public int maxProfit(int[] prices) {
    int n = prices.length;
    int[] dp = new int[2];
    dp[1] = Integer.MIN_VALUE;
    for (int x : prices) {
        dp[0] = Math.max(dp[0], dp[1] + x);
        dp[1] = Math.max(dp[1], -x);
    }
    return dp[0];
}

变题二：交易无限次

题目详情可见 买卖股票的最佳时机 II

x
public int maxProfit(int[] prices) {
    int n = prices.length;
    int[][] dp = new int[n + 1][2];
    dp[0][1] = Integer.MIN_VALUE;
    for (int i = 1; i <= n; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1]);
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i - 1]);
    }
    return dp[n][0];
}
// 空间优化
public int maxProfit(int[] prices) {
    int n = prices.length;
    int[] dp = new int[2];
    dp[1] = Integer.MIN_VALUE;
    for (int x : prices) {
        int t = dp[0];
        dp[0] = Math.max(dp[0], dp[1] + x);
        dp[1] = Math.max(dp[1], t - x);
    }
    return dp[0];
}

变题三：交易两次

题目详情可见 买卖股票的最佳时机 III

变题四的特殊化情况！！(k = 2)

x
public int maxProfit(int[] prices) {
    int n = prices.length, k = 2;
    int[][][] dp = new int[n + 1][k + 1][2];
    for (int i = 0; i <= n; i++) dp[i][0][1] = Integer.MIN_VALUE;
    for (int i = 0; i <= k; i++) dp[0][i][1] = Integer.MIN_VALUE;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i - 1]);
            dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i - 1]);
        }
    }
    return dp[n][k][0];
}

变题四：交易 K 次

题目详情可见 买卖股票的最佳时机 IV

变题三的一般化情况！！

x
public int maxProfit(int k, int[] prices) {
    int n = prices.length;
    int[][][] dp = new int[n + 1][k + 1][2];
    for (int i = 0; i <= n; i++) dp[i][0][1] = Integer.MIN_VALUE;
    for (int i = 0; i <= k; i++) dp[0][i][1] = Integer.MIN_VALUE;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i - 1]);
            dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i - 1]);
        }
    }
    return Math.max(dp[n][k][0], dp[n][k][1]);
}

变题五：交易多次 & 有手续费

题目详情可见 买卖股票的最佳时机含手续费

x
public int maxProfit(int[] prices, int fee) {
    int n = prices.length;
    int[][] dp = new int[n + 1][2];
    dp[0][1] = Integer.MIN_VALUE;
    for (int i = 1; i <= n; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1]);
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - fee - prices[i - 1]);
    }
    return dp[n][0];
}
// 空间优化
public int maxProfit(int[] prices, int fee) {
    int n = prices.length;
    int[] dp = new int[2];
    dp[1] = Integer.MIN_VALUE;
    for (int x : prices) {
        int t = dp[0];
        dp[0] = Math.max(dp[0], dp[1] + x);
        dp[1] = Math.max(dp[1], t - fee - x);
    }
    return dp[0];
}

变题六：交易多次 & 有冷冻期

题目详情可见 最佳买卖股票时机含冷冻期

x
public int maxProfit(int[] prices) {
    int n = prices.length;
    int[][] dp = new int[n + 1][2];
    dp[0][1] = Integer.MIN_VALUE;
    for (int i = 1; i <= n; i++) {
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i - 1]);
        dp[i][1] = Math.max(dp[i - 1][1], (i - 2 >= 0 ? dp[i - 2][0] : 0) - prices[i - 1]);
    }
    return dp[n][0];
}