122. 买卖股票的最佳时机 II（c++/动态规划）

class Solution {
public:
    int maxProfit(vector& prices) {
        int n = prices.size();
        int dp[n][2];
        dp[0][0] = 0;//没有股票
        dp[0][1] = -prices[0];//持有股票
        for(int i = 1; i < n; i++){
            dp[i][0] = max(dp[i-1][0],dp[i-1][1] + prices[i]);//当天没有股票 = max(前一天没有持有股票，前一天有股票+当天卖掉获得收益price[i])
            dp[i][1] = max(dp[i-1][1],dp[i-1][0] - prices[i]);//当天持有股票 = max(前一天没持有股票，前一天没有股票-当天买入股票花费price[i])

        }
        return dp[n-1][0];//没有持有股票的收益更大
    }
};

优化空间：

class Solution {
public:
    int maxProfit(vector& prices) {
        int n = prices.size();
        int dp0 = 0;//没有股票
        int dp1 =  -prices[0];//持有股票
        for(int i = 1; i < n; i++){
            int newdp0 = max(dp0,dp1 + prices[i]);
            int newdp1 = max(dp1,dp0 - prices[i]);
            dp0 = newdp0;
            dp1 = newdp1;
        }
        return dp0;
    }
};