股票问题第二波

发表于 分类于 Disqus： 本文字数： 610 阅读时长 ≈ 2 分钟

上一篇文章：股票问题与状态机dp

本篇文章涉及题目如下：

交易K次问题

在上篇文章的基础上，我们其实需要做的就是在处理函数上加一个参数k代表还可以交易几次，当k < 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
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        vector<vector<vector<int>>> cache(n, vector<vector<int>>(k + 1, vector<int>(2, -1)));
        function<int(int, int, bool)> dfs = [&](int i, int k, bool hold) {
            if (k < 0) {
                return INT_MIN;
            }
            if (i < 0) {
                return hold ? INT_MIN : 0;
            }
            int& res = cache[i][k][hold];
            if (res != -1) {
                return res;
            }
            if (hold) {
                // 第i天持有
                return res = max(dfs(i - 1, k, true), dfs(i - 1, k, false) - prices[i]);
            }
            // 第i天未持有
            return res = max(dfs(i - 1, k,  false), dfs(i - 1, k - 1, true) + prices[i]);
        };
        return dfs(n - 1, k, false);
    }
};

值得注意的是，该问题的记忆化搜索实现中cache数组应该为三维，cache[i][k][hold]表示第i天，剩余交易次数k次、是否拥有股票的结果的缓存

使用记忆化搜索是无法通过123. 买卖股票的最佳时机 III的，因此可以将其改成dp解决

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 k = 2;
        int n = prices.size();
        vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(k + 2, vector<int>(2, INT_MIN)));
        for (int j = 0; j < k + 2; j++) {
            dp[0][j][0] = 0;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= k + 1; j++) {
                dp[i + 1][j][0] = max(dp[i][j][0], dp[i][j - 1][1] + prices[i]);
                dp[i + 1][j][1] = max(dp[i][j][1], dp[i][j][0] - prices[i]);
            }
        }
        return dp[n][k + 1][0];
    }
};

冷冻期问题

这个问题有点类似与打家劫舍—不能连续偷相邻的房屋。那么在本问题中，是不是将比较前一天的代码改成比较前前一天的代码就行了？差不多！但是只有在买入股票或卖出股票的时候需要修改，这是因为买入卖出才算一次交易，所以在这两个时间段选一个进行修改即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> cache(n, vector(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) {
                return res = max(dfs(i - 1, true), dfs(i - 2, false) - prices[i]);
            }
            return res = max(dfs(i - 1, false), dfs(i - 1, true) + prices[i]);
        };
        return dfs(n - 1, false);
    }
};