代码中有注释,需要注意的一点是dp[10000][3]定义的是第i天结束后的状态。用0表示持有股票,1表示不持有,2表示冷冻期
代码:
class Solution {
public:
int dp[10000][3]; //dp定义了第i天结束后的状态,0代表不持有,1代表持有,2代表是冷冻期
int maxProfit(vector<int>& prices) {
int size=prices.size();
if(size==0)
return 0;
dp[0][0]=0;
dp[0][2]=0;
dp[0][1]=-prices[0];
for(int i=1;i<size;i++){
dp[i][0]=max(dp[i-1][0],dp[i-1][2]);
dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);
//若今天结束后是冷冻期,那么今天一定卖出了一支股票。所以昨天结束的状态一定是持有一支股票,即dp[i-1][1]
dp[i][2]=dp[i-1][1]+prices[i];
}
return max(dp[size-1][0],dp[size-1][2]);
}
};