动态规划 - 买卖股票的最佳时机2

class Solution {
public:
    int maxProfit(vector& prices) {
        
        int length = prices.size();
        int  dp[length][2];

        dp[0][1] = -prices[0];
        dp[0][0] = 0;
        for (int i = 1;i < length;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[length - 1][0];

    

    }
};

，当天存在手中有股票与无股票两种状态。
其中 dp[i][0]表示第i天手里没有股票。 dp[i][1]表示第i天手里有股票。

边界条件就是第一天的状态。
不买股票就是 dp[0][0].
买了股票就是 dp[0][1] - prices[0]

最后一天肯定是手中没有股票收益最大。所以输出 dp[length -1] [0].