1.題目

2.思路

比之前的I題【LeetCode121】買賣股票的最佳時機（附dp總結圖）多了條件：可以多次買賣，但不能同時參與多筆交易，

——因此區別就是:
d p [ i ] [ 1 ] dp[i][1] dp[i][1]即第i天持股時的狀態，2種可能情況：
1）前一天持股，
2）前一天不持股，即今天買了股票（現金數減少prices[i]），由于整個程序只交易一次，所以今天是整個程序的第一次買股票，即第i天的現金數為 d p [ i ? 1 ] [ 0 ] ? p r i c e s [ i ] dp[i-1][0]-prices[i] dp[i?1][0]?prices[i]，所以 d p [ i ] [ 1 ] = m a x ( d p [ i ? 1 ] [ 1 ] , d p [ i ? 1 ] [ 0 ] ? p r i c e s [ i ] ) dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]) dp[i][1]=max(dp[i?1][1],dp[i?1][0]?prices[i])，

3.代碼

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        if(n==0||n==1){
            return 0;
        }
        vector<vector<int>>dp(n,vector<int>(2));
        dp[0][0]=0;
        dp[0][1]=0-prices[0];
        for(int i=1;i<n;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[n-1][0];//最后一天結束不持股
    }
};