算法003 买卖股票系列

参考LeetCode团灭买卖股票系列

DP[i][j][k]:  i:天数   j: 交易次数 k: 持有或不持有股票, 定义: 当第i天交易j次后持有或不持有股票最赚钱的情况

---

不持有股票: DP[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + price[i]);

没有持有股票，两种可能，昨天没持有股票，今天不买 / 昨天持有股票，今天卖出股票

持有股票：DP[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - price[i]);

两种可能，昨天持有股票，没有卖/昨天没有持有股票，今天买

---

四个Base Case:

dp[-1][k][0] = 0

解释：因为 i 是从 0 开始的，所以 i = -1 意味着还没有开始，这时候的利润当然是 0 。

dp[-1][k][1] = -infinity

解释：还没开始的时候，是不可能持有股票的，用负无穷表示这种不可能。

dp[i][0][0] = 0

解释：因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0 。

dp[i][0][1] = -infinity

解释：不允许交易的情况下，是不可能持有股票的，用负无穷表示这种不可能。

---

从中可以推算出六题全部的做法

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/solution/yi-ge-tong-yong-fang-fa-tuan-mie-6-dao-gu-piao-wen/

https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/solution/gu-piao-jiao-yi-xi-lie-cong-tan-xin-dao-dong-tai-g/