其实也是动态规划的一种变形，总的来说，是定义一个二维数组dp[i][j],i表示的是天数，j表示的状态，总的表示收益。
最基础的就是有两种状态，dp[i][0]表示未持有股票，dp[i][1]表示持有股票。
用动态规划的思想：dp[i][0]，dp[i][1]都是从dp[i-1]推得的。
只买卖一次：
点击查看代码
dp[i][0] = max(dp[i - 1][0], -prices[i]);
dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
多次买卖：
点击查看代码
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]); // 注意这里是和121. 买卖股票的最佳时机唯一不同的地方。
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
限制次数的买卖：
dp[i][0] = dp[i - 1][0];
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
就是需要多添加一些状态。
一般形式：
点击查看代码
for(int i=1;i<sz;i++){
for(int j=0;j<=2*k;j++){
if(j==0){dp[i][j]=dp[i-1][j];}
else if(j%2==1){
dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]-prices[i]);
}
else if(j%2==0){
dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+prices[i]);
}
}
}
有冷冻期这题也是需要确定有几个状态：
点击查看代码
for(int i=1;i<sz;i++){
dp[i][0]=max(dp[i-1][0],dp[i-1][3]);
dp[i][1]=max(dp[i-1][1],max(dp[i-1][0]-prices[i],dp[i-1][3]-prices[i]));
dp[i][2]=dp[i-1][1]+prices[i];
dp[i][3]=dp[i-1][2];
}