股票问题

每天都有三种「选择」：买入、卖出、无操作，我们用 buy, sell, rest 表示这三种选择。
但问题是，并不是每天都可以任意选择这三种选择的，因为 sell 必须在 buy 之后，buy 必须在 sell 之后。那么 rest 操作还应该分两种状态，一种是 buy 之后的 rest（持有了股票），一种是 sell 之后的 rest（没有持有股票）。而且别忘了，我们还有交易次数 k 的限制，就是说你 buy 还只能在 k > 0 的前提下操作。
这个问题的「状态」有三个，第一个是天数，第二个是允许交易的最大次数，第三个是当前的持有状态（即之前说的 rest 的状态，我们不妨用 1 表示持有，0 表示没有持有）。

  1. //我昨天持有股票，且截至昨天最大交易次数限制为 k；
  2. //但是今天我 sell 了，所以我今天没有持有股票了，最大交易次数限制依然为 k。
  3. dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
  4.               max( 今天选择 rest,        今天选择 sell       )
  6. //我昨天本没有持有，且截至昨天最大交易次数限制为 k - 1；
  7. //但今天我选择 buy，所以今天我就持有股票了，最大交易次数限制为 k。
  8. dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
  9.               max( 今天选择 rest,         今天选择 buy         )

这里着重提醒一下，时刻牢记「状态」的定义，状态 k 的定义并不是「已进行的交易次数」，而是「最大交易次数的上限限制」。如果确定今天进行一次交易，且要保证截至今天最大交易次数上限为 k，那么昨天的最大交易次数上限必须是 k - 1。买入卖出算一次交易。

  1. dp[-1][...][0] = 0
  2. 解释：因为 i 是从 0 开始的，所以 i = -1 意味着还没有开始，这时候的利润当然是 0。
  4. dp[-1][...][1] = -infinity
  5. 解释：还没开始的时候，是不可能持有股票的。
  6. 因为我们的算法要求一个最大值，所以初始值设为一个最小值，方便取最大值。
  8. dp[...][0][0] = 0
  9. 解释：因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0。
  11. dp[...][0][1] = -infinity
  12. 解释：不允许交易的情况下，是不可能持有股票的。
  13. 因为我们的算法要求一个最大值，所以初始值设为一个最小值，方便取最大值。

总结：

  1. //base case：
  2. dp[-1][...][0] = dp[...][0][0] = 0
  3. dp[-1][...][1] = dp[...][0][1] = -infinity
  5. //状态转移方程：
  6. dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
  7. dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])