leetcode 3573(买卖股票问题，状态机dp）

3573: 买卖股票的最佳时机Ⅴ

思路：状态机（买卖股票问题）

• dfs(i,j,0) 表示在 prices[0] 到 prices[i] 中完成至多 j 笔交易，第 i 天结束时未持有股票的最大利润。
• dfs(i,j,1) 表示在 prices[0] 到 prices[i] 中完成至多 j 笔交易，第 i 天结束时持有股票的最大利润。dfs(i,j,2) 表示在 prices[0] 到 prices[i] 中完成至多 j 笔交易，第 i 天结束时处于做空中（空头状态）的最大利润。

此外，对于 dfs(i,j,0)，在计算最大值时额外考虑在第 i 天买回股票（平空）的情况，即 dfs(i,j,2)−prices[i]。

vector<array<long long,3>> f(k+2,{LLONG_MIN/2,LLONG_MIN/2,LLONG_MIN/2});

下标 0~k+1（三个状态 - 二维数组）

class Solution { public: long long maximumProfit(vector<int>& prices, int k) { int n=prices.size(); vector<array<long long,3>> f(k+2,{LLONG_MIN/2,LLONG_MIN/2,LLONG_MIN/2}); for(int j=1;j<=k+1;j++) f[j][0]=0; //保证f[j-1]不越界，j从1开始 for(int p:prices){ for(int j=k+1;j>0;j--){ f[j][0]=max(f[j][0],max(f[j][1]+p,f[j][2]-p)); f[j][1]=max(f[j][1],f[j-1][0]-p); f[j][2]=max(f[j][2],f[j-1][0]+p); } } return f[k+1][0]; } };