188. Best Time to Buy and Sell Stock IV

 1 class Solution { 2 public: 3     int maxProfit(int k, vector<int> &prices) { 4         int n = prices.size(); 5         if (k * 2 >= n) { 6             int res = 0; 7             for (int i = 1; i < n; i++) { 8                 res += prices[i] > prices[i-1] ? prices[i] - prices[i-1] : 0; 9             }10             return res;11         }12         vector<vector<int> > dp(k + 1, vector<int>(n, 0));13         //一次交易是先买入再卖出的一个完正过程14         //dp[i][0]意味着只能当天买入卖出，所以dp[i][0]=015         //dp[0][i]意味着没有交易的次数，所以dp[0][i]=016         for (int i = 1; i <= k; i++) {17             int localmax = -prices[0];18             for (int j = 1; j < n; j++) {19                 //dp[i][j] 表示的是前j天最多使用i次交易时（第j天可以卖出）的利润。（1<=i<=k，0<=j<n）20                 dp[i][j] = max(dp[i][j-1], localmax + prices[j]);21                 //localmax表示的是最多使用i次交易，使用最多前j-1个价格，最后买入price[j]后的最大利润22                 localmax = max(localmax, dp[i-1][j-1] - prices[j]);23             }24         }25         return dp[k][n-1];26     }27 };