代码随想录算法训练营第36期DAY53

DAY53

309最佳买卖股票时机含冷冻期

0 状态1：持有股票。

Dp[i][0]=max(dp[i-1][0],dp[i-1][3]-price[i],price[i-1][2]-price[i])

针对不持有（关键点）：

1 状态2：是继承的不持有。A.昨天为冷静期，前天卖出。B.昨天就不持有

Dp[i][1]=max(dp[i-1][3],dp[i-1][1])

2 状态3：今天卖出股票

Dp[i][2]=dp[i-1][0]+price[i]

3 状态4：冷冻期。注意冷冻期显然是无法卖股票的，因为手上没有股票

Dp[i][3]=dp[i-1][2]

滚动数组不好想，直接二维吧。

1. class Solution {
2. public:
3.     int maxProfit(vector<int>& prices) {
4.         vector<vector<int>>dp(prices.size(),vector<int>(4,0));
5.         dp[0][0]=-1*prices[0];
6.         for(int i=1;i<prices.size();i++){
7.             dp[i][0]=max(max(dp[i-1][0],dp[i-1][1]-prices[i]),dp[i-1][3]-prices[i]);
8.             dp[i][1]=max(dp[i-1][3],dp[i-1][1]);
9.             dp[i][2]=dp[i-1][0]+prices[i];
10.             dp[i][3]=dp[i-1][2];
11.         }
12.         return max(max(dp[prices.size()-1][1],dp[prices.size()-1][2]),dp[prices.size()-1][3]);
13.     }
14. };

714买卖股票的最佳时机含手续费

注意初始化，不要初始化dp[1]=-fee；因为这样不如不买，（0元）。直接在for循环里求dp[1] 因为用不到刚开始dp[1]。

1. class Solution {
2. public:
3.     int maxProfit(vector<int>& prices, int fee) {
4.         vector<int> dp(2);
5.         dp[0]=-1*prices[0];
6.         for(int i=1;i<prices.size();i++){
7.             dp[0]=max(dp[0],dp[1]-prices[i]);
8.             dp[1]=max(dp[1],dp[0]+prices[i]-fee);
9.         }
10.         if(max(dp[0],dp[1])<0) return 0;
11.         return max(dp[0],dp[1]);
12.     }
13. };