分析
设f[i][j][k]表示第i天进行第j笔交易的股票状态的最大收益。
k=0表示手中无货,k=1表示手中有货。
状态转移方程为:
f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]+prices[i-1]);
f[i][j][1]=max(f[i-1][j][1],f[i-1][j-1][0]-prices[i-1]);
最后答案是手中无货(k=0)状态下进行j<=2笔交易时的最大收益
C++ 代码
class Solution {
public:
int ans;
int maxProfit(vector<int>& prices) {
int n=prices.size();
int f[n+1][3][2];
memset(f,-0x3f,sizeof f);
for(int i=0;i<=n;i++) f[i][0][0]=0; //预处理表示第i天进行0笔交易时手中无货的收益为0
for(int i=1;i<=n;i++)
{
for(int j=1;j<=2;j++)
{
f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]+prices[i-1]);
f[i][j][1]=max(f[i-1][j][1],f[i-1][j-1][0]-prices[i-1]);
}
}
for(int i=0;i<=2;i++) ans=max(ans,f[n][i][0]); //答案为第n天进行小于等于2笔交易且手中无货的收益的最大值
return ans;
}
};