题目

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例

1
2
3
4
输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

解题思路

这道题的解决方案实际上承袭了II的思路，只不过有个地方需要考虑，它引入了一个至多交易次数，所以我们只需要再引入一个j作为一个次数的衡量基准就行了，II的题解见状态机DP无冷却期股票问题II，这里我们需要注意的是：每一天都有一个这样的表
| 最多允许卖出 j 次 | 不持有 hold = 0 | 持有 hold = 1 |
|—-|—-|—-|
| j = 0 | memo[i][0][0] | memo[i][0][1] |
| j = 1 | memo[i][1][0] | memo[i][1][1] |
| j = 2 | memo[i][2][0] | memo[i][2][1] |

我们需要用一个vector把他们包成一个数组，同时上面这个表格本身也是一个vector<array<int,2>>的一个数组，同时，买入和卖出这两个动作构成一个交易，所以在j变动的时候，只需要动一次就行。

代码实现

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
class Solution {
private:
    vector<vector<array<int,2>>>memo;
public:
    int dfs(int i,int j,bool hold,vector<int>&prices){
        if (j<0){
            return INT_MIN;
        }
        int ans;
        if (i<0&&hold==0){
            return 0;
        }
        if (i<0&&hold==1){
            return INT_MIN;
        }
        if(memo[i][j][hold]!=INT_MIN){
            return memo[i][j][hold];
        }
        if(hold==0){
            ans=max(dfs(i-1,j,0,prices),dfs(i-1,j-1,1,prices)+prices[i]);
        }else{
            ans=max(dfs(i-1,j,1,prices),dfs(i-1,j,0,prices)-prices[i]);
        }
        memo[i][j][hold]=ans;
        return ans;
    }
    int maxProfit(vector<int>& prices) {
        memo.assign(prices.size(),vector<array<int, 2>>(3, array<int, 2>{INT_MIN, INT_MIN}));
        int ans=dfs(prices.size()-1,2,0,prices);
        return ans;
    }
};

复杂度分析

  • 时间复杂度：O(n)
  • 空间复杂度：O(n)

易错点

这个j的取值非常容易混淆，并且也要详细理解为什么选择使用一个vector<vector<array<int,2>>>来构建这个memo