股票问题II与状态机dp

本篇文章思路来源于 @bilibili/灵茶山艾府

题目描述：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii

相对于买卖股票的最佳时机 I，该问题可以多次买入和卖出股票以获取最大利益

启发思路

以 prices = [7,1,5,3,6,4] 为例，直到最后一天，我们能获取到的最大利润是什么？

最后一天，也就是第五天的利润（下标从 0 开始） = 第 0 天到第 5 天结束的利润 = 第 0 天到第四天结束的利润 + 第五天的利润

将利润分为两部分：

第五天的利润
1. 什么都不做
2. 买入股票（从未持有股票 -> 持有股票）
3. 卖出股票（从持有股票 -> 未持有股票）
第零天到第四天的利润

由此可以清晰的感受到这样一个大问题可以分割为相同的子问题：

问题：第 i 天结束，持有/未持有股票的最大利润

子问题：第 i - 1 天结束，持有/未持有股票的最大利润

状态机

简单的理解就是状态的转换，如下图就是本题的状态机

那么如何将状态机与思路结合起来呢？

我们可以这么想：

假设 f(i, false) 代表第 i 天结束时未拥有股票的利润，f(i, true) 代表第 i 天结束时拥有股票的利润
第 i 天未持有股票的情况为：第 i-1 天未持有股票或者第 i-1 天拥有股票但是第 i 天时卖出了股票。这时第 i 天未持有股票的最大利润为 f(i, false) = max(f(i - 1, false), f(i - 1, true) + prices[i])
第 i 天持有股票的情况未：第 i-1 天持有股票或者第 i-1 天未拥有股票但是第 i 天时买入了股票。这时第 i 天持有股票的最大利润为 f(i, true) = max(f(i - 1, true), f(i - 1, false) - prices[i])

记忆化搜索

使用上面的思路，采用递归的方法，不难写出下面的算法：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        auto f = [&](this auto&& f, int i, bool hold) {
            if (i < 0) {
                return hold ? INT_MIN : 0;
            }
            if (hold) {
                return max(f(i - 1, false) - prices[i], f(i - 1, true));
            }
            return max(f(i - 1, true) + prices[i], f(i - 1, false));
        };
        return f(n - 1, false);
    }
};

上面还有几个问题

为什么当 i 不在范围时 return hold ? INT_MIN : 0;？当 i 不在范围内，那么说明此时就算拥有股票也是非法的，那么其返回值一定不能影响到正常的 i 值，而用于比较返回值的函数为 max，那么将该返回值设置成 INT_MAX 就是最好的选择了
为什么最后只要返回 dfs(n - 1, false)？这时因为最后一天卖出去（也就是未持有股票，false）所拥有的利润一定比最后一天不卖出去（持有股票，true）所拥有的利润高，因此也每次要返回 max(dfs(n - 1, false), dfs(n - 1, true)) 了

好，这时点击提交！会发现超时了！这时因为我们在递归的过程中重复计算了子问题，造成了不必要的开销

如图，以上红色的部分都是重复的，我们应该在计算的时候保存它们，这就是记忆化搜索

需要注意的是，记忆化数组 cache 初始化应该为 -1 而不是 0,是因为计算的利润有可能是 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
27
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> memo(n, vector<int>(2, -1));
        auto f = [&](this auto&& f, int i, bool hold) {
            if (i < 0) {
                return hold ? INT_MIN : 0;
            }
            
            int ret = memo[i][hold];
            if (ret != -1) {
                return ret;
            }

            if (hold) {
                ret = max(f(i - 1, false) - prices[i], f(i - 1, true));
            } else {
                ret = max(f(i - 1, true) + prices[i], f(i - 1, false));
            }
            
            memo[i][hold] = ret;
            return ret;
        };
        return f(n - 1, false);
    }
};

递推为 dp

由以上的记忆化搜索和状态机思路，就不难将其 1：1 翻译为递推了：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2, -1));
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for (int i = 1; i < n; ++i) {
            dp[i][0] = max(dp[i - 1][1] + prices[i], dp[i - 1][0]);
            dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1]);
        }
        return dp[n - 1][0];
    }
};