//188. 买卖股票的最佳时机 IV

使用二维数组 dp[i][j] ：第i天的状态为j，所剩下的最大现金是dp[i][j]
j的状态表示为：

  • 0 表示不操作
  • 1 第一次买入
  • 2 第一次卖出
  • 3 第二次买入
  • 4 第二次卖出
  • …..

除了0以外，偶数就是卖出，奇数就是买入。

  1. class Solution {
  2. public:
  3.     int maxProfit(int k, vector<int>& prices) {
  5.         if (prices.size() == 0) return 0;
  6.         vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0));
  7.         for (int j = 1; j < 2 * k; j += 2) {
  8.             dp[0][j] = -prices[0];
  9.         }
  10.         for (int i = 1;i < prices.size(); i++) {
  11.             for (int j = 0; j < 2 * k - 1; j += 2) {
  12.                 //第j次买入 卖出
  13.                 dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
  14.                 dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
  15.             }
  16.         }
  17.         return dp[prices.size() - 1][2 * k];
  18.     }
  19. };