股票买卖问题

• 状态转移框架
  • dp[i][k][1]：表示今天是第 i 天，手上持有股票，至今最多允许交易https://qimok.cn k 次
  • dp[i][k][0]：表示今天是第 i 天，手上没有持有股票，至今最多允许交易 k 次

/**
 * 解释：今天我没有持有股票，有两种可能：
 *     1、要么是我昨天就没有持有，然后今天选择 rest，所以我今天还是没有持有；
 *     2、要么是我昨天持有股票，但是我今天 sell 了，所以我今天没有持有股票了。
 *            max(    选择 rest，           选择 sell           )
 */           
dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])

/**
 * 解释：今天我持有着股票，有两种可能：
 *     1、要么我昨天就持有着股票，然后今天选择 rest，所以我今天还持有着股票；
 *     2、要么我昨天本没有持有，但今天我选择 buy，所以今天我就持有股票了。
 *            max(   选择 rest，             选择 buy               )
 */
dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])

• base case：

// 因为 i 是从 0 开始的，所以 i = -1 意味着还没有开始，这时候的利润为 0
dp[-1][k][0] = 0;

// 还没开始的时候，是不可能持有股票的，用负无穷表示这种情况不可能
dp[-1][k][1] = -infinity

// 因为 k 是从 1 开始，所以 k = 0 意味着不允许交易，这时候利润当然是 0
dp[i][0][0] = 0;

// 不允许交易的情况下，是不可能持有股票的，用负无穷表示这种情况不可能
dp[i][0][1] = -infinity

• 归纳、总结：

// base case：
dp[-1][k][0] = dp[i][0][0] = 0;
dp[-1][k][1] = dp[i][0][1] = -infinity;
// 状态转移方程：
dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
dp[i][k][1] = max(dp[i -1][k][1], dp[i - 1][k - 1][0] - prices[i]);

下面就通过上面的葵花宝典来斩杀以下 6 道题目：

• 买卖股票的https://qimok.cn最佳时机
• 买卖股票的最佳时机 II
• 买卖股票的最佳时机 言七墨III
• 买卖股票的最佳时机 IV
• 最佳买卖股票时机含冷冻期
• 买卖股票的最佳时机含手续费

/**
 * >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> 解法一：k == 1 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
 * <p>
 *    由于本题要求的交易次数为1，故得到转移方程：
 *    dp[i][1][0] = max(dp[i - 1][1][0], dp[i - 1][1][1] + prices[i])
 *    dp[i][1][1] = max(dp[i - 1][1][1], dp[i - 1][0][0] - prices[i])  
 *    解释：已知当 k = 0 时，dp[i - 1][0][0] = 0。
 *            故 dp[i][1][1] = max(dp[i - 1][1][1], -prices[i])
 *
 *    现在发现 k 都是 1，不会改变，即 k 对状态转移已经没有影响了。
 *    可以进一步简化去掉所有 k，即
 *    dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
 *    dp[i][1] = max(dp[i - 1][1], -prices[i])
 *    base case：
 *        dp[0][0] = 0;
 *        dp[0][1] = -prices[i];
 */
public int maxProfit1(int[] prices) {
    int len = prices.length;
    if (len == 0) {
        return 0;
    }
    int[][] dp = new int[len][2];
    for (int i = 0; i < len; i++) {
        if (i - 1 == -1) {
            dp[i][0] = 0;
            dp[i][1] = -prices[i];
            continue;
        }
        dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
        dp[i][1] = Math.max(dp[i - 1][1], - prices[i]);
    }
    return dp[len - 1][0]; // 第二维参数：[1] 代表手上还持有股票，[0] 表示手上的股票已经卖出去了，很显然后者得到的利润一定大于前者
}

/**
 * >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> 解法二：k == 1 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
 * 状态压缩
 */
public int maxProfit2(int[] prices) {
    int len = prices.length;
    if (len == 0) {
        return 0;
    }
    // dp[-1][0] = 0, dp[-1][1] = -infinity
    int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
    for (int i = 0; i < len; i++) {
        // dp[i][0] = max(dp[i - 1][0], dp[i][1] + prices[i])
        dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
        // dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
        dp_i_1 = Math.max(dp_i_1, -prices[i]);
    }
    return dp_i_0; // dp_i_1 代表手上还持有股票，dp_i_0 表示手上的股票已经卖出去了，很显然后者得到的利润一定大于前者
}

/**
 * >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> k = +infinity <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
 * 如果 k 为正无穷，那么可以认为 k 和 k - 1 是一样的。可以这样改写框架：
 *      dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i])
 *      dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i])
 *                    = max(dp[i - 1][k][1], dp[i - 1][k][0] - prices[i])
 *      现在发现数组中的 k 已经不会改变了，也就是说不需要记录 k 这个状态了：
 *      dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
 *      dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
 */
public int maxProfit(int[] prices) {
    int len = prices.length;
    if (len == 0) {
        return 0;
    }
    // dp[-1][0] = 0, dp[-1][1] = -infinity
    int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
    for (int i = 0; i < len; i++) {
        // dp_i_0 等价于状态转移方程中的 dp[i - 1][0]
        int temp = dp_i_0;
        // dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
        dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
        // dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i])
        dp_i_1 = Math.max(dp_i_1, temp - prices[i]);
    }
    return dp_i_0;
}

/**
     * >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> k = 2 <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
     * k = 2 和前面题目的情况稍微不同，因为上面的情况都和 k 的关系不太大。要么 k 是正无穷，状态转移和 k 没关系了；要么 k = 1，跟 k = 0 这个 base case 挨得近，最后也没有存在感。
     * 这道题 k = 2 和后面要讲的 k 是任意正整数的情况中，对 k 的处理就凸显出来了
     * 状态转移方程：
     *     dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
     *     dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]);
     * base case：
     *     dp[0][k][0] = dp[i][k][0] = 0;
     *     dp[0][k][1] = dp[i][k][1] = -prices[0]; // 由状态转移方程可知，当 i = 0 时，dp[0][k][1] = max(dp[-1][k][1], dp[-1][k - 1][0] - prices[i])，
     *     而 dp[0 - 1][k -  1][0] = 0; 因为 i 是从 0 开始的，所以 i = -1 意味着还没有开始，这时候的利润为 0，故 dp[0][k][1] = -prices[0]
     */
    public int maxProfit(int[] prices) {
        int len = prices.length;
        if (len == 0) {
            return 0;
        }
        int maxK = 2;
        int dp[][][] = new int[len][maxK + 1][2];
        for (int i = 0; i < len; i++) {
            for (int k = maxK; k > 0; k--) { // 由于没有消掉 k 的影响，所以必须要对 k 进行穷举
                if (i - 1 == -1) {
                    dp[i][k][0] = 0;
                    dp[i][k][1] = -prices[i];
                    continue;
                }
                dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
                dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]);
            }
        }
        return dp[len - 1][maxK][0];
    }

/**
 * >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> k = any integer <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
 * 一次交易由买入和卖出构成，至少需要两天。所以说有效的限制 k 应该不超过 len/2，如果超过，就没有约束作用了，相当于 k = +infinity
 * 无约束：走`2、买卖股票的最佳时机 II`的逻辑
 * 有约束：
 * 状态转移方程：
 *     dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
 *     dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]); 
 * base case：
 *     dp[0][k][0] = dp[i][k][0] = 0;
 *     dp[0][k][1] = dp[i][k][1] = -prices[0]; // 由状态转移方程可知，当 i = 0 时，dp[0][k][1] = max(dp[-1][k][1], dp[-1][k - 1][0] - prices[i])，
 *     而 dp[0 - 1][k -  1][0] = 0; 因为 i 是从 0 开始的，所以 i = -1 意味着还没有开始，这时候的利润为 0，故 dp[0][k][1] = -prices[0]
 */
public int maxProfit(int k, int[] prices) {
    int len = prices.length;
    if (len == 0) {
        return 0;
    }
    if (k > len / 2) {
        return maxProfit(prices); // 调用`2、买卖股票的最佳时机 II`中的代码
    }
    int[][][] dp = new int[len][k + 1][2];
    for (int i = 0; i < len; i++) {
        for (int j = k; j > 0; j--) {
            if (i - 1 == -1) {
                dp[i][j][0] = 0;
                dp[i][j][1] = -prices[i];
                continue;
            }
            dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
            dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
        }
    }
    return dp[len - 1][k][0];
}

/**
 * >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> k = +infinity with cooldown <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
 * base case：
 *     dp[-1][0] = 0;
 *     dp[-1][1] = -infinity;
 * 状态转移方程：
 *     dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
 *     dp[i][1] = max(dp[i - 1][1], dp[i - 2][0] - prices[i])
 * 解释：由于存在冷冻期，第 i 天选择 buy 的时候，要从 i-2 的状态转移，而不是 i-1 。
 */
public int maxProfit4(int[] prices) {
    int len = prices.length;
    if (len == 0) {
        return 0;
    }
    // dp[-1][0] = 0, dp[-1][1] = -infinity
    int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
    // dp[i - 2][0] = 0
    int dp_pre_0 = 0; 
    for (int i = 0; i < len; i++) {
        int temp = dp_i_0;
        dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
        dp_i_1 = Math.max(dp_i_1, dp_pre_0 - prices[i]);
        dp_pre_0 = temp;
    }
    return dp_i_0; // dp_i_1 代表手上还持有股票，dp_i_0 表示手上的股票已经卖出去了，很显然后者得到的利润一定大于前者
}

/**
 * >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> k = +infinity with fee <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
 * base case：
 *     dp[-1][0] = 0;
 *     dp[-1][1] = -infinity;
 * 每次交易要支付手续费，只要把手续费从利润中减去即可。改写方程：
 *      dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
 *      dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i] - fee)
 * 解释：相当于买入股票的价格升高了。
 * 在第一个式子里减也是一样的，相当于卖出股票的价格减小了。
 */
public int maxProfit(int[] prices, int fee) {
    int len = prices.length;
    if (len == 0) {
        return 0;
    }
    // dp[-1][0] = 0, dp[-1][1] = -infinity
    int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
    for (int i = 0; i < len; i++) {
        int temp = dp_i_0;
        dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
        dp_i_1 = Math.max(dp_i_1, temp - prices[i] - fee);
    }
    return dp_i_0; // dp_i_1 代表手上还持有股票，dp_i_0 表示手上的股票已经卖出去了，很显然后者得到的利润一定大于前者
}