题目：买卖股票的最佳时机 IV

原题链接

当每次状态转移只依赖于上一个状态时，可以通过机械方式将 dp 问题的空间优化为滚动数组：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  int maxProfit(int k, vector<int>& prices) {
    int n = prices.size();
    // 第一维设置为 2
    vector<vector<int>> f(2, vector<int>(k + 1, -1e8));
    auto g = f;
    int res = 0;
    f[0][0] = 0;
    for (int i = 1; i <= n; i++) {
      for (int j = 0; j <= k; j++) {
        // 第一维都加上 & 1，相当于模 2，从而在 f[0] 和 f[1] 进行滚动
        f[i & 1][j] = max(f[i - 1 & 1][j], g[i - 1 & 1][j] + prices[i - 1]);
        g[i & 1][j] = g[i - 1 & 1][j];
        if (j)
          g[i & 1][j] = max(g[i & 1][j], f[i - 1 & 1][j - 1] - prices[i - 1]);
        res = max(res, f[i & 1][j]);
      }
    }
    return res;
  }
};