股票问题与状态机dp

发表于 分类于 Disqus： 本文字数： 1.1k 阅读时长 ≈ 4 分钟

本篇文章思路来源于 @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. 第五天的利润
    1. 什么都不做
    2. 买入股票（从 未持有股票 -> 持有股票）
    3. 卖出股票（从 持有股票 -> 未持有股票）
  2. 第零天到第四天的利润

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

问题：第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
17
18
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        function<int(int, bool)> dfs = [&](int i , bool hold) {
            if (i < 0) {
                return hold ? INT_MIN : 0;
            }
            if (hold) {
                // 第i天持有
                return max(dfs(i - 1, true), dfs(i - 1, false) - prices[i]);
            }
            // 第i天未持有
            return max(dfs(i - 1, false), dfs(i - 1, true) + prices[i]);
        };
        return dfs(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>> cache(n, vector<int>(2, -1));
        function<int(int, bool)> dfs = [&](int i , bool hold) {
            if (i < 0) {
                return hold ? INT_MIN : 0;
            }
            int res = cache[i][hold];
            if (res != -1) {
                return res;
            }
            if (hold) {
                // 第i天持有
                res = max(dfs(i - 1, true), dfs(i - 1, false) - prices[i]);
                cache[i][hold] = res;
                return res;
            }
            // 第i天未持有
            res = max(dfs(i - 1, false), dfs(i - 1, true) + prices[i]);
            cache[i][hold] = res;
            return res;
        };
        return dfs(n - 1, false);
    }
};

递推为dp

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

但由于dp[i - 1][hold]中的i - 1可能为一个负数，故我们需要在dp前添加一个哨兵位，且i都变为i + 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 + 1, vector<int>(2, 0));
        dp[0][0] = 0;
        dp[0][1] = INT_MIN;
        for (int i = 0; i < n; i++) {
            dp[i + 1][0] = max(dp[i][0], dp[i][1] + prices[i]);
            dp[i + 1][1] = max(dp[i][1], dp[i][0] - prices[i]);
        }
        return dp[n][0];
    }
};