代码随想录 打卡第四十天

121 买卖股票的最佳时机class Solution { public: int maxProfit(vectorint prices) { vectorint state(2,0); vectorvectorint dp(prices.size(),state); dp[0][0] -prices[0]; for(int i 1;i prices.size();i){ dp[i][0] max(dp[i-1][0],-prices[i]); dp[i][1] max(dp[i-1][1],dp[i-1][0]prices[i]); } return dp[prices.size()-1][1]; } };122 买卖股票的最佳时机 IIclass Solution { public: int maxProfit(vectorint prices) { vectorint state(2,0); vectorvectorint dp(prices.size(),state); dp[0][0] -prices[0]; for(int i 1;i prices.size();i){ dp[i][0] max(dp[i-1][0],dp[i-1][1]-prices[i]); dp[i][1] max(dp[i-1][1],dp[i-1][0]prices[i]); } return dp[prices.size()-1][1]; } };123 买卖股票的最佳时机 IIIclass Solution { public: int maxProfit(vectorint prices) { vectorint state(5,0); vectorvectorint dp(prices.size(),state); dp[0][0] 0; dp[0][1] -prices[0]; dp[0][2] 0; dp[0][3] -prices[0]; dp[0][4] 0; for(int i 1;i prices.size();i){ dp[i][0] dp[i-1][0]; 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]prices[i]); dp[i][3] max(dp[i-1][3],dp[i-1][2]-prices[i]); dp[i][4] max(dp[i-1][4],dp[i-1][3]prices[i]); } return dp[prices.size()-1][4]; } };注意初始化时机理解状态转移的过程