买卖股票的最佳时机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];
    }
};