代码随想录50——动态规划： 123买卖股票的最佳时机III、188买卖股票的最佳时机IV

1. 123买卖股票的最佳时机III

参考：代码随想录， 123买卖股票的最佳时机III；力扣题目链接

1.1.题目

1.2.解答

注意：下面的讲解基本按照代码随想录网站上的讲解来的，但是有改动，因为代码随想录上使用的一天是五个状态，但是感觉其实并不太好理解，所以下面自己修改成了一天四个状态，更加好理解，而且能和昨天的两道题对应上，是一样的思路。

这道题目相对 121.买卖股票的最佳时机 和 122.买卖股票的最佳时机II难了不少。关键在于至多买卖两次，这意味着可以买卖一次，可以买卖两次，也可以不买卖。

1.确定dp数组以及下标的含义

一天一共就有四个状态，

• 第一次 持有
• 第一次 不持有
• 第二次 持有
• 第二次 不持有

dp[i][j]中 i表示第i天，j为 [0 - 3] 四个状态，dp[i][j]表示第i天状态j所剩最大现金。

注意：这个地方代码随想录中给出的是五个状态：

没有操作
第一次买入
第一次卖出
第二次买入
第二次卖出
1
2
3
4
5

但是后面又说了，这里的买入/卖出不是表示动作，而是表示一种状态，按照昨天的题目来说应该说是持有/不持有。所以说这样其实并不好理解，尤其是**“没有操作”**这个状态，到底表示持有还是不持有？所以实际上还是用四个状态，用是否持有来表示更加好理解一点。

2.确定递推公式

（1）达到dp[i][0]状态，即第一次持有，有两个具体操作：

• 操作一：第i天买入股票了，那么dp[i][0] = - prices[i]。注意：由于这里是第一次持有，所以之前没有任何买入卖出操作，之前剩余的钱就是0，所以今天买入之后，剩余的钱就是0-prices[i]。
• 操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i][1] = dp[i - 1][0]

那么dp[i][0]究竟选 - prices[i]，还是dp[i - 1][0]呢？
一定是选最大的，所以 dp[i][0] = max(- prices[i], dp[i - 1][0]);

（2）达到dp[i][1]状态，即第一次不持有，有两个具体操作：

• 操作一：第i天卖出股票了，那么dp[i][1] = dp[i - 1][0] + prices[i]
• 操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][1] = dp[i - 1][1]

所以 dp[i][1] = max(dp[i - 1][0] + prices[i], dp[i - 1][0])

（3）达到dp[i][2]状态，即第二次持有，有两个具体操作：

• 操作一：第i天买入股票了，那么dp[i][2] = dp[i-1][1] - prices[i]。注意：由于这里是第二次持有，所以之前是有第一次买入然后卖出的操作的，所以之前剩余的钱就是dp[i-1][1]，所以今天买入之后，剩余的钱就是dp[i-1][1] - prices[i]。
• 操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i][2] = dp[i - 1][2]

所以 dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] - prices[i]);

（4）达到dp[i][3]状态，即第二次不持有，有两个具体操作：

• 操作一：第i天卖出股票了，那么dp[i][3] = dp[i - 1][2] + prices[i]
• 操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][3] = dp[i - 1][3]

所以 dp[i][3] = max(dp[i - 1][2] + prices[i], dp[i - 1][3])

3.dp数组如何初始化

• 第0天做第一次买入的操作，dp[0][0] = -prices[0];

• 第0天做第一次卖出的操作，就是先原价买入，再原价卖出，所以结果就是0，即所以dp[0][1] = 0;

• 第0天做第二次买入的操作，同理和第一次买入一样，dp[0][2] = -prices[0];

• 第0天做第一次卖出的操作，同理和第一次卖出一样，就是先原价买入，再原价卖出，所以结果就是0，即所以dp[0][3] = 0;

4.确定遍历顺序

从递归公式其实已经可以看出，一定是从前向后遍历，因为dp[i]，依靠dp[i - 1]的数值。

5.举例推导dp数组
这里就给出代码随想录中五个状态的递推数组吧。注意：其实可以发现其中dp[i][0]表示没有操作的状态，始终是0，所以根本没有必要加入这个状态。

最后给出上面四个状态的代码，自己写的，也是可以AC的，而且按照上面的讲解思路和昨天的题目一样，更容易理解。

int maxProfit(vector<int> &prices)
{
    if(prices.empty())
        return 0;

    // 1.定义dp数组：行数为股票价格天数，列数为4，分别表示
    // 第1次持有股票、第1次不持有股票、第2次持有股票、第2次不持有股票的最多剩余的钱
    vector<vector<int>> dp(prices.size(), vector<int>(4, 0));  

    // 2.dp数组初始化
    dp[0][0] = -prices[0];   // 第一次持有：-prices[0]
    dp[0][1] = 0;            // 第一次不持有：0
    dp[0][2] = -prices[0];   // 第二次持有：-prices[0]
    dp[0][3] = 0;            // 第二次不持有：0

    // 3.动态规划：递推
    for(int i = 1; i < prices.size(); i++)
    {
        // 第一次持有：昨天就第一次持有，或者 今天才第一次持有，
        // 即今天第一次买入（结果就是-prices[i]，因为之前剩余的钱就是0）
        dp[i][0] = max(dp[i-1][0], -prices[i]);

        // 第一次不持有：昨天就第一次不持有，或者 今天才第一次不持有，
        // 即今天第一次卖出（结果是昨天第一次持有剩余的钱 + 今天卖出收获的钱）
        dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);
        
        // 第二次持有：昨天就第二次持有，或者 今天才第二次持有，
        // 即今天第二次买入（结果就是dp[i-1][1]-prices[i]，因为之前剩余的钱就是昨天第一次不持有）
        dp[i][2] = max(dp[i-1][2], dp[i-1][1] - prices[i]);

        // 第二次不持有：昨天就第二次不持有，或者 今天才第二次不持有，
        // 即今天第二次卖出（结果就是昨天第二次持有剩余的钱 + 今天卖出收获的钱）
        dp[i][3] = max(dp[i-1][3], dp[i-1][2] + prices[i]);
    }

    // 最后返回结果：肯定是不持有股票剩余的钱最多
    return max(dp[prices.size()-1][1], dp[prices.size()-1][3]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

2. 188买卖股票的最佳时机IV

参考：代码随想录，188买卖股票的最佳时机IV；力扣题目链接

2.1.题目

2.2.解答

这道题目其实并不难，简直可以说和上一道题目一模一样。只不过是把次数换成k次，所以我们使用一个for循环来遍历第k次持有/不持有剩余的最大钱数即可。

仍然使用上面的代码，也就是没有无操作这种状态，每一次只有持有/不持有两个状态，这样k次的话，最后就有2*k种状态。

int maxProfit(int k, vector<int> &prices)
{
    if(prices.empty())
        return 0;
    
    // 1.定义dp数组：一天有2*k种状态，表示第k次持有/不持有股票
    vector<vector<int>> dp(prices.size(), vector<int>(2*k, 0));

    // 2.初始化dp数组：0/2/...表示持有，1/3/表示不持有
    for(int j = 0; j < k; j++)
        dp[0][2*j] = -prices[0];

    // 3.动态规划进行递推
    for(int i = 1; i < prices.size(); i++)
    {
        // 注意：第1此持有/不持有的状态需要单独处理，无法写到for循环中！
        // 第1次持有：昨天就第1次持有，或者昨天第1次不持有，
        // 今天刚买入，就是在昨天不持有的钱 - 今天的价格
        dp[i][0] = max(dp[i-1][0], -prices[i]);
        // 第1次不持有：昨天就第1次不持有，或者今天刚卖出，就是在昨天持有的钱 + 今天的价格
        dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]);

        for(int j = 1; j < k; j++)
        {   
            // 第j次持有：昨天就第j次持有，或者昨天第j-1次不持有，
            // 今天刚买入，就是在昨天第j-1次不持有的钱 - 今天的价格
            dp[i][2*j] = max(dp[i-1][2*j], dp[i-1][2*j-1] - prices[i]);
            
            // 第j次不持有：昨天就第j次不持有，或者昨天第j次持有，
            // 今天刚卖出，就是在昨天持有的钱 + 今天的价格
            dp[i][2*j+1] = max(dp[i-1][2*j+1], dp[i-1][2*j] + prices[i]);
        }
    }

    // 最后，在所有不持有的结果中寻找最大值
    int result = 0;
    for(int j = 0; j < k; j++)
        result = dp[prices.size()-1][2*j+1] > result ? dp[prices.size()-1][2*j+1] : result;
    
    return result;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

注意：上面的代码中就发现不添加无操作这种状态带来的弊端了，就是对于第一次的持有/不持有状态需要单独写，也就是代码中for(j = 1;)前面需要单独写j=0的情况。本质上是因为第一次持有的时候，前面没有买入卖出操作 ，所以上一次的操作剩余的钱就是0。但是由于我们没有维护上一次的操作（也就是如果使用无操作这个状态的话，把他赋值成0就可以了），这样也就无法使用统一的上一次不持有的最大钱数 - 本次的价格来得到本次持有的最大钱数。

所以这样来看的话，虽然代码随想录上使用一个无操作的状态不太容易理解，但是在代码编程实现上更方便，因为可以使用同一个公式，这样可以使用for(j = 0)的循环把k次的状态都写到一个循环语句中。