最佳买卖股票时机含冷冻期
动态规划
确定dp数组以及下标的含义
- 0：持有股票（包括之前买的和今天买的）
- 1：不持有股票（包括之前没买和今天卖了）
- 2：冷静期（包括之前是冷静期和昨天卖了）
确定递推公式
- 0：持有股票
dp[i][0] = max( dp[i-1][0] , dp[i-1][2] - prices[i] ); - 1：不持有股票
- dp[i][1] = max( dp[i-1][1] , dp[i-1][0] + prices[i] );
- 2：冷静期
dp[i][2] = max( dp[i-1][2] , dp[i-1][1]);
dp数组如何初始化
- dp[0][0] = -prices[0];
- dp[0][1] = 0；
- dp[0][2] = 0;
class Solution { public: int maxProfit(vector<int>& prices) { if(prices.size() <=1 ) return 0; vector<vector<int>> dp(prices.size() , vector<int>(3,0)); dp[0][0] = -prices[0]; dp[0][1] = 0; dp[0][2] = 0; for(int i=1; i<prices.size();i++) { dp[i][0] = max( dp[i-1][0] , dp[i-1][2] - prices[i] ); 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]); } return dp[prices.size()-1][1]; } };
二刷
class Solution { public: int maxProfit(vector<int>& prices) { vector<vector<int>> dp(prices.size() , vector<int>(3 ,0)); dp[0][0] = -prices[0];//持有股票 dp[0][1] = 0; //不持有 dp[0][2] = 0; //冷静 for(int i=1 ; i<prices.size() ;i++) { dp[i][0] = max(dp[i-1][0] , dp[i-1][2] - prices[i] ); dp[i][1] = max(dp[i-1][1] , dp[i-1][0] + prices[i] ); dp[i][2] = dp[i-1][1]; } return max( dp[prices.size()-1][1] , dp[prices.size()-1][2] ); } };
