代码随想录49——动态规划：121买卖股票的最佳时机、122买卖股票的最佳时机II

1.121买卖股票的最佳时机

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

1.1.题目

1.2.解答

1.2.1.贪心算法

因为股票就买卖一次，那么贪心的想法很自然就是取最左最小值，取最右最大值，那么得到的差值就是最大利润。

C++代码如下：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int low = INT_MAX;
        int result = 0;
        for (int i = 0; i < prices.size(); i++) {
            low = min(low, prices[i]);  // 取最左最小价格
            result = max(result, prices[i] - low); // 直接取最大区间利润
        }
        return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

时间复杂度：$O(n)$
空间复杂度：$O(1)$

注意：这道题目用贪心算法的解释大概是这么个意思，但是还是理解的不是特别透彻。

1.2.2.动态规划

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

• dp[i][0] 表示第i天持有股票所得最多现金。这里可能有同学疑惑，本题中只能买卖一次，持有股票之后哪还有现金呢？
  其实一开始现金是0，那么加入第i天买入股票现金就是 -prices[i]， 这是一个负数。

• dp[i][1] 表示第i天不持有股票所得最多现金

注意这里说的是“持有”，“持有”不代表就是当天“买入”！也有可能是昨天就买入了，今天保持持有的状态。

2.确定递推公式

（1）如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来：

• 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
• 第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]

那么dp[i][0]应该选所得现金最大的，所以dp[i][0] = max(dp[i - 1][0], -prices[i]);

（2）如果第i天不持有股票即dp[i][1]， 也可以由两个状态推出来：

• 第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]
• 第i天卖出股票，所得现金就是按照今天股票佳价格卖出后所得现金即：prices[i] + dp[i - 1][0]

同样dp[i][1]取最大的，dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);

3.dp数组如何初始化

由递推公式 dp[i][0] = max(dp[i - 1][0], -prices[i]); 和 dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);可以看出，其基础都是要从dp[0][0]和dp[0][1]推导出来。

• dp[0][0]表示第0天持有股票，此时的持有股票就一定是买入股票了，因为不可能有前一天推出来，所以dp[0][0] -= prices[0];

• dp[0][1]表示第0天不持有股票，不持有股票那么现金就是0，所以dp[0][1] = 0;

4.确定遍历顺序

从递推公式可以看出dp[i]都是有dp[i - 1]推导出来的，那么一定是从前向后遍历。

5.举例推导dp数组

以示例1，输入：[7,1,5,3,6,4]为例，dp数组状态如下：

最后给出自己写的代码，注意自己把上面dp数组的索引换了一下，感觉dp[i][0]表示不持有股票、dp[i][1]表示持有股票更加好一点。

int maxProfit(vector<int> &prices)
{
    // 1.dp数组：dp[i][0]表示第i天不持有股票剩下的钱，dp[i][1]表示持有股票剩下的钱
    vector<vector<int>> dp(prices.size(), vector<int>(2, 0)); 

    // 2.dp数组初始化：第0天不持有股票，剩下的钱就是0；第0天持有股票，剩下的钱是-prices[i]
    dp[0][0] = 0;
    dp[0][1] = -prices[0];

    // 3.动态规划：使用状态转移方程递推
    for(int i = 1; i < prices.size(); i++)
    {
        // 不持有股票的剩下的钱：
        // 1.昨天就不持有，则剩下的钱不变；
        // 2.今天卖出，则 剩下的钱 = prices[i] + dp[i-1][1]，即 今天卖出得到的钱+昨天持有股票的剩下的钱
        dp[i][0] = max(dp[i-1][0], prices[i] + dp[i-1][0]);
        
        // 持有股票剩下的钱：
        // 1.昨天就持有股票，则剩下的钱不变，仍然是dp[i-1][1]
        // 2.今天才刚持有股票，则需要花钱今天买入，则剩下的钱是-prices[i]
        dp[i][1] = max(dp[i-1][1], -prices[i]);
    }

    // 最终剩下最多的钱，肯定是不持有股票得到的
    return dp[prices.size()-1][0];  
}
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

注意：这道题目和昨天的动态规划二叉树的题目差不多，也是dp数组有两个维度，每个维度都表示持有/不持有 或者 选择/不选择得到的最优结果。这样可以保证每一个局部都是最优的，然后通过递推公式传递结果，从而达到全局最优。

2.122买卖股票的最佳时机II

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

2.1.题目

2.2.解答

本题在讲解贪心专题的时候就已经讲解过了 贪心算法：买卖股票的最佳时机II ，只不过没有深入讲解动态规划的解法，那么这次我们再好好分析一下动规的解法。

本题和 121. 买卖股票的最佳时机 的唯一区别本题股票可以买卖多次了（注意只有一只股票，所以再次购买前要出售掉之前的股票）

在动规五部曲中，这个区别主要是体现在递推公式上，其他都和121. 买卖股票的最佳时机都一样。

这里重申一下dp数组的含义：

• dp[i][0] 表示第i天持有股票所得现金
• dp[i][1] 表示第i天不持有股票所得最多现金

（1）如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来

• 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]
• 第i天买入股票，所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即：dp[i - 1][1] - prices[i]

注意这里和121. 买卖股票的最佳时机唯一不同的地方，就是推导dp[i][0]的时候，第i天买入股票的情况：

• 在121. 买卖股票的最佳时机中，因为股票全程只能买卖一次，所以如果买入股票，那么第i天持有股票即dp[i][0]一定就是 -prices[i]，因为之前没有剩余的钱，也就是剩余的钱是0.

• 而本题，因为一只股票可以买卖多次，所以当第i天买入股票的时候，所持有的现金可能有之前买卖过的利润。那么第i天持有股票即dp[i][0]，如果是第i天买入股票，所得现金就是昨天不持有股票的所得现金 减去 今天的股票价格， 即：dp[i - 1][1] - prices[i]。

（2）再看如果第i天不持有股票即dp[i][1]的情况， 依然可以由两个状态推出来

• 第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]
• 第i天卖出股票，所得现金就是按照今天股票佳价格卖出后所得现金即：prices[i] + dp[i - 1][0]

注意这里和121. 买卖股票的最佳时机就是一样的逻辑，卖出股票收获利润（可能是负值）天经地义！

最后给出代码如下，和上一道题目基本上是一样的。

int maxProfit(vector<int> &prices)
{
    // 1.定义dp数组：dp[i][0]第i天不持有股票最多剩余的钱；dp[i][1]第i天持有股票最多剩余的钱
    vector<vector<int>> dp(prices.size(), vector<int>(2, 0));
    
    // 2.初始化dp数组
    dp[0][0] = 0;
    dp[0][1] = -prices[0];

    // 3.动态规划：利用递推公式开始递推
    for(int i = 1; i < prices.size(); i++)
    {
        // 今天不持有股票剩余的最多的钱：1.昨天就不持有； 2.昨天持有，今天卖出
        dp[i][0] = max(dp[i-1][0], prices[i] + dp[i-1][1]);

        // 今天持有股票剩余最多的钱：1.昨天就持有；2.今天刚买入：昨天不持有的钱 - 今天购入花的钱
        // 注意：这个地方由于可以多次买卖股票，所以昨天不持有股票剩余的钱未必是0，而是dp[i-1][0]
        dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);
    }

    // 4.最后剩余最多的钱，一定是最后一天不持有股票剩余的钱
    return dp[prices.size()-1][0];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23