团灭 LeetCode 股票买卖问题

 1 dp[i][k][0 or 1]
 2 0 <= i <= n-1, 1 <= k <= K
 3 n 为天数，大 K 为最多交易数
 4 此问题共 n × K × 2 种状态，全部穷举就能搞定。
 5 
 6 for 0 <= i < n:
 7     for 1 <= k <= K:
 8         for s in {0, 1}:
 9             dp[i][k][s] = max(buy, sell, rest)
10 
11 
12 总结：
13 利润的最大值：dp[n-1][k][0],其中1 <= k <= K
14 base case：计算 i==0
15 dp[-1][k][0] = dp[i][0][0] = 0
16 dp[-1][k][1] = dp[i][0][1] = -infinity
17 
18 状态转移方程：
19 dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
20 dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
21 //注意：卖出之后才算一次交易,所以才有dp[i-1][k][1]和dp[i-1][k-1][0]