参考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
解释:不允许交易的情况下,是不可能持有股票的,用负无穷表示这种不可能。
从中可以推算出六题全部的做法