题解 | #股票交易的最大收益（二）#

/*
dp(i,j)
j = 0: 手上没有股票，没有交易
j = 1: 手上买了一只股票
j = 2 : 手上无股票，卖了一只股票
j = 3 ： 买了第二只股票
j = 4 : 手上无股票，卖了第二只股票

第一次交易有三种状态：
1, 不操作 dp(i, 0) = dp(i-1, 0)
2, 第一次买 dp(i,1) = max(dp(i-1,1), dp(i-1, 0) + price(i))
3, 第一次卖 
当天操作或，当天没有操作
dp(i,2) = max(dp(i-1, 1) + price(i), dp(i-1,2))


股票第二次交易，有五种状态
1,2,3
4, 第二次购买
当天买/当天没有操作
dp(i,j) = dp(i-1,3)/ dp(i-1,2) - prices(i);
5, 第二次卖出
当天买/当天没有操作
dp(i-1,3) + prices(i), dp(i-1, 4);

*/

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