买卖股票的最佳时机IV
确定dp数组以及下标的含义
- 没操作
- 持有股票（包括之前买的和今天买的）
- 不持有股票（包括之前没买和今天卖了）
dp[i][j]中 i表示第i天，j为 k*2+1 个状态，dp[i][j]表示第i天状态j所剩最大现金。
确定递推公式
- 达到持有状态，有两个具体操作：
- 第i天买入股票了，那么dp[i][j] (j%2==1) = dp[i-1][j-1] - prices[i]
- 第i天没有操作，而是沿用前一天买入的状态，
即：dp[i [j] = dp[i - 1][j] (j%2==1)
- 达到不持有状态，也有两个操作：
- 第i天卖出股票了，那么dp[i]j = dp[i - 1][j-1] + prices[i]
- 第i天没有操作，沿用前一天卖出股票的状态，
即：dp[i][j] = dp[i - 1][j] (j%2==0)
dp数组如何初始化
- dp[0][0] = 0;
- dp[0][j] = -prices[0]; (j%2==1)
- dp[0][j] = 0; (j%2==0)
class Solution { public: int maxProfit(int k, vector<int>& prices) { if(prices.size()<= 1) return 0; vector<vector<int>> dp(prices.size(),vector<int>( k*2+1 ,0)); for(int j=0 ; j < k*2+1 ; j++) { if(j%2 == 1) dp[0][j] = -prices[0];//持有股票 // cout<<dp[0][j]<<' '; } // cout<<endl; for(int i=1 ;i<prices.size() ; i++) { for(int j=0 ; j< k*2+1 ;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] ); // cout<<dp[i][j]<<' '; } // cout<<endl; } return dp[prices.size()-1][k*2]; } };
二刷
class Solution { public: int maxProfit(int k, vector<int>& prices) { vector<vector<int>> dp(prices.size() , vector<int>(k*2+1)); for(int i=0 ; i<(k*2+1) ;i++) if(i%2 == 1) dp[0][i] = -prices[0]; for(int i=1 ; i<prices.size() ;i++) { for(int j=1 ; j<(k*2+1) ;j++) { if(j%2==1) dp[i][j] = max(dp[i-1][j] , dp[i-1][j-1] - prices[i] ); else dp[i][j] = max(dp[i-1][j] , dp[i-1][j-1] + prices[i] ); } } return dp[prices.size()-1][k*2]; } };
