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