题解 | #买卖股票的最好时机(三)#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 两次交易所能获得的最大收益
     * @param prices int整型vector 股票每一天的价格
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        // write code here
        const int len = prices.size();
        int k=2;
        vector<vector<vector<int>>> dp(len,vector<vector<int>>(k+1,vector<int>(2)));//note k+1
        for(int i=0;i<len;i++){
            for(int j=k;j>=1;j--){//note >=1
                if(i==0){
                    dp[i][j][0]=-prices[i];
                    continue;//note
                }
                dp[i][j][1]=max(dp[i-1][j][1],dp[i-1][j][0]+prices[i]);
                dp[i][j][0]=max(dp[i-1][j][0],dp[i-1][j-1][1]-prices[i]);//j-1 note
            }
        }
//         return dp[len-1][0][2];
        return dp[len-1][k][1];
    }
};

参考
https://labuladong.github.io/algo/3/28/96/