DP笔记(13)：区间DP——买卖股票问题
Author：zhoulujun Date：
股票系列问题已经属于动态规划问题中较困难的了
买卖股票问题合集
买卖股票的最佳时机（121. Best Time to Buy and Sell Stock）：只能进行一次交易，求最大利润。
买卖股票的最佳时机 II（122. Best Time to Buy and Sell Stock II）：可以进行多次交易（买卖股票多次），求最大利润。
买卖股票的最佳时机 III（123. Best Time to Buy and Sell Stock III）：最多可以进行两次交易，求最大利润。
买卖股票的最佳时机 IV（188. Best Time to Buy and Sell Stock IV）：最多可以进行 k 次交易，求最大利润。
最佳买卖股票时机含冷冻期（309. Best Time to Buy and Sell Stock with Cooldown）：可以进行多次交易，但每次卖出后有一天的冷冻期，求最大利润。
买卖股票的最佳时机含手续费（714. Best Time to Buy and Sell Stock with Transaction Fee）：可以进行多次交易，每次交易需要手续费，求最大利润。
这 6 道题目是有共性的，我们只需要抽出来力扣第 188 题「买卖股票的最佳时机 IV」进行研究，因为这道题是最泛化的形式，其他的问题都是这个形式的简化
第一题是只进行一次交易，相当于 k = 1；第二题是不限交易次数，相当于 k = +infinity（正无穷）；第三题是只进行 2 次交易，相当于 k = 2；剩下两道也是不限次数，但是加了交易「冷冻期」和「手续费」的额外条件，其实就是第二题的变种，都很容易处理。
这些股票问题的核心思想是通过动态规划来记录和更新每一天的两种状态：
持有股票（持仓）：这一天结束时持有股票所能获得的最大利润。
不持有股票（空仓）：这一天结束时不持有股票所能获得的最大利润。
基于这些状态，通过每天的操作（买入、卖出、保持不动等）来更新状态，并最终求得最大利润。例如，对于第一个问题，状态转移方程如下：
hold[i] = max(hold[i-1], -prices[i]) 表示第 i 天持有股票的状态。
sold[i] = max(sold[i-1], hold[i-1] + prices[i]) 表示第 i 天不持有股票的状态。
我们通过记录和更新每天的持仓和空仓状态来求解最大利润。虽然它们都可以归为线性动态规划，但根据问题的具体条件和限制，可能会涉及更复杂的状态转移和额外的条件判断。
比如说这个问题，每天都有三种「选择」：买入、卖出、无操作，我们用 buy, sell, rest 表示这三种选择。
但问题是，并不是每天都可以任意选择这三种选择的，因为 sell 必须在 buy 之后，buy 必须在 sell 之后。那么 rest 操作还应该分两种状态，一种是 buy 之后的 rest（持有了股票），一种是 sell 之后的 rest（没有持有股票）。而且别忘了，我们还有交易次数 k 的限制，就是说你 buy 还只能在 k > 0 的前提下操作。
这个问题的「状态」有三个：
第一个是天数
第二个是允许交易的最大次数
第三个是当前的持有状态（即之前说的 rest 的状态，我们不妨用 1 表示持有，0 表示没有持有）。
然后我们用一个三维数组就可以装下这几种状态的全部组合：
dp[i][k][0 or 1]
0 <= i <= n - 1, 1 <= k <= K
n 为天数，大 K 为交易数的上限，0 和 1 代表是否持有股票。
此问题共 n × K × 2 种状态，全部穷举就能搞定。
for 0 <= i < n:
for 1 <= k <= K:
for s in {0, 1}:
dp[i][k][s] = max(buy, sell, rest)而且我们可以用自然语言描述出每一个状态的含义，比如说 dp[3][2][1] 的含义就是：今天是第三天，我现在手上持有着股票，至今最多进行 2 次交易。再比如 dp[2][3][0] 的含义：今天是第二天，我现在手上没有持有股票，至今最多进行 3 次交易。很容易理解，对吧？
我们想求的最终答案是 dp[n - 1][K][0]，即最后一天，最多允许 K 次交易，最多获得多少利润。
状态转移框架
只看「持有状态」，可以画个状态转移图：
通过这个图可以很清楚地看到，每种状态（0 和 1）是如何转移而来的。根据这个图，我们来写一下状态转移方程：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]) max( 今天选择 rest, 今天选择 sell )
解释：今天我没有持有股票，有两种可能，我从这两种可能中求最大利润：
我昨天就没有持有，且截至昨天最大交易次数限制为 k；然后我今天选择 rest，所以我今天还是没有持有，最大交易次数限制依然为 k。
我昨天持有股票，且截至昨天最大交易次数限制为 k；但是今天我 sell 了，所以我今天没有持有股票了，最大交易次数限制依然为 k。
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]) max( 今天选择 rest, 今天选择 buy )
解释：今天我持有着股票，最大交易次数限制为 k，那么对于昨天来说，有两种可能，我从这两种可能中求最大利润：
我昨天就持有着股票，且截至昨天最大交易次数限制为 k；然后今天选择 rest，所以我今天还持有着股票，最大交易次数限制依然为 k。
我昨天本没有持有，且截至昨天最大交易次数限制为 k - 1；但今天我选择 buy，所以今天我就持有股票了，最大交易次数限制为 k。
这里着重提醒一下，时刻牢记「状态」的定义，状态 k 的定义并不是「已进行的交易次数」，而是「最大交易次数的上限限制」。如果确定今天进行一次交易，且要保证截至今天最大交易次数上限为 k，那么昨天的最大交易次数上限必须是 k - 1。举个具体的例子，比方说要求你的银行卡里今天至少有 100 块钱，且你确定你今天可以赚 10 块钱，那么你就要保证昨天的银行卡要至少剩下 90 块钱。
这个解释应该很清楚了，如果 buy，就要从利润中减去 prices[i]，如果 sell，就要给利润增加 prices[i]。今天的最大利润就是这两种可能选择中较大的那个。
注意 k 的限制，在选择 buy 的时候相当于开启了一次交易，那么对于昨天来说，交易次数的上限 k 应该减小 1。
这里补充修正一点，以前我以为在 sell 的时候给 k 减小 1 和在 buy 的时候给 k 减小 1 是等效的，但细心的读者向我提出质疑，经过深入思考我发现前者确实是错误的，因为交易是从 buy 开始，如果 buy 的选择不改变交易次数 k 的话，会出现交易次数超出限制的的错误。
现在，我们已经完成了动态规划中最困难的一步：状态转移方程。如果之前的内容你都可以理解，那么你已经可以秒杀所有问题了，只要套这个框架就行了。不过还差最后一点点，就是定义 base case，即最简单的情况。
dp[-1][...][0] = 0
解释：因为 i 是从 0 开始的，所以 i = -1 意味着还没有开始，这时候的利润当然是 0。
dp[-1][...][1] = -infinity
解释：还没开始的时候，是不可能持有股票的。
因为我们的算法要求一个最大值，所以初始值设为一个最小值，方便取最大值。
dp[...][0][0] = 0
解释：因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0。
dp[...][0][1] = -infinity
解释：不允许交易的情况下，是不可能持有股票的。
因为我们的算法要求一个最大值，所以初始值设为一个最小值，方便取最大值。
把上面的状态转移方程总结一下：
base case： dp[-1][...][0] = dp[...][0][0] = 0 dp[-1][...][1] = dp[...][0][1] = -infinity 状态转移方程： dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]) dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
读者可能会问，这个数组索引是 -1 怎么编程表示出来呢，负无穷怎么表示呢？这都是细节问题，有很多方法实现。现在完整的框架已经完成，下面开始具体化。
买卖股票的最佳时机
直接套状态转移方程，根据 base case，可以做一些化简：
dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i]) dp[i][1][1] = max(dp[i-1][1][1], dp[i-1][0][0] - prices[i]) = max(dp[i-1][1][1], -prices[i])
解释：k = 0 的 base case，所以 dp[i-1][0][0] = 0。
现在发现 k 都是 1，不会改变，即 k 对状态转移已经没有影响了。
可以进行进一步化简去掉所有 k：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]) dp[i][1] = max(dp[i-1][1], -prices[i])
这就是常规的解答：
我们要得到dp[i][0]：表示第i天持有股票能获取的最大利润，显然有两种情况：
一种是第i-1天就持有股票，注意理解题意，我们只能买入一次股票如果第i-1天持有，那么第i天的股票来自于第i-1天，即dp[i][0]=dp[i-1][0]；
一种是第i-1天不持有，需要在今天买入，即dp[i][0]=-prices[i]。我们只需要选择这两种情况种较大的那一种即可，dp[i][0]=Math.max(dp[i-1][0],-prices[i])。
我们要得到dp[i][1]：表示第i天不持有股票能获取的最大利润。，同样也有两种情况，一种是第i-天就没有持有股票，那正好我们啥也不用做，即dp[i][1]=dp[i-1][1]；另一种是第i-1天持有股票，需要我们在今天把他卖出，即dp[i][1]=dp[i-1][0]+prices[i]。我们只需要选择这两种情况种较大的那一种即可，dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+prices[i])。
综上分析，递推公式如下:
dp[i][0]=Math.max(dp[i-1][0],-prices[i]); dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]+prices[i])
代码
var maxProfit_k_1 = function(prices) {
var n = prices.length;
var dp = new Array(n).fill(0).map(() => new Array(2).fill(0));
for (var i = 0; i < n; i++) {
if (i - 1 == -1) {
// 基础情况，可以单独提取出去，i从1开始
dp[i][0] = 0;
dp[i][1] = -prices[i];
continue;
}
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
}
return dp[n - 1][0];
};优化空间复杂度的版本
var maxProfit_k_1 = function(prices) {
var n = prices.length;
// 基础情况: dp[-1][0] = 0, dp[-1][1] = 负无穷
var dp_i_0 = 0, dp_i_1 = -Infinity;
for (var i = 0; i < n; i++) {
// dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
// dp[i][1] = max(dp[i-1][1], -prices[i])
dp_i_1 = Math.max(dp_i_1, -prices[i]);
}
return dp_i_0;
};可以参考 https://programmercarl.com/0121.买卖股票的最佳时机.html
买卖股票的最佳时机 II
题目还专门强调可以在同一天出售，但我觉得这个条件纯属多余，如果当天买当天卖，那利润当然就是 0，这不是和没有进行交易是一样的吗？这道题的特点在于没有给出交易总数 k 的限制，也就相当于 k 为正无穷。
如果 k 为正无穷，那么就可以认为 k 和 k - 1 是一样的。可以这样改写框架：
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]) dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]) = max(dp[i-1][k][1], dp[i-1][k][0] - prices[i]) 我们发现数组中的 k 已经不会改变了，也就是说不需要记录 k 这个状态了： dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]) dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
直接翻译成代码：
var maxProfit_k_inf = function(prices) {
var n = prices.length;
var dp = Array.from(Array(n), () => Array(2).fill(0));
for (var i = 0; i < n; i++) {
if (i - 1 == -1) {
// base case
dp[i][0] = 0;
dp[i][1] = -prices[i];
continue;
}
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}
return dp[n - 1][0];
}空间复杂度优化版本
var maxProfit_k_inf = function(prices) {
var n = prices.length;
var dp_i_0 = 0, dp_i_1 = Number.MIN_VALUE;
for (var i = 0; i < n; i++) {
var temp = dp_i_0;
dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
dp_i_1 = Math.max(dp_i_1, temp - prices[i]);
}
return dp_i_0;
}可参考 https://programmercarl.com/0122.买卖股票的最佳时机II（动态规划）.html
最佳买卖股票时机含冷冻期
也就是 k 为正无穷，但含有交易冷冻期的情况：
和上一道题一样的，只不过每次 sell 之后要等一天才能继续交易，只要把这个特点融入上一题的状态转移方程即可：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]) dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])
解释：第 i 天选择 buy 的时候，要从 i-2 的状态转移，而不是 i-1 。
var maxProfit_with_cool = function(prices) {
let n = prices.length;
let dp = new Array(n).fill(null).map(() => new Array(2).fill(0));
for (let i = 0; i < n; i++) {
if (i - 1 == -1) {
// base case 1
dp[i][0] = 0;
dp[i][1] = -prices[i];
continue;
}
if (i - 2 == -1) {
// base case 2
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
// i - 2 小于 0 时根据状态转移方程推出对应 base case
dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
// dp[i][1]
// = max(dp[i-1][1], dp[-1][0] - prices[i])
// = max(dp[i-1][1], 0 - prices[i])
// = max(dp[i-1][1], -prices[i])
continue;
}
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
dp[i][1] = Math.max(dp[i-1][1], dp[i-2][0] - prices[i]);
}
return dp[n - 1][0];
};空间优化：
var maxProfit_with_cool = function(prices) {
let n = prices.length;
let dp_i_0 = 0;
let dp_i_1 = Number.MIN_SAFE_INTEGER;
let dp_pre_0 = 0; // 代表 dp[i-2][0]
for (let i = 0; i < n; i++) {
let temp = dp_i_0;
dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
dp_i_1 = Math.max(dp_i_1, dp_pre_0 - prices[i]);
dp_pre_0 = temp;
}
return dp_i_0;
};可以参 https://programmercarl.com/0309.最佳买卖股票时机含冷冻期.html#思路
买卖股票的最佳时机反观其他思路
暴⼒
这道题⽬最直观的想法，就是暴⼒，找最优间距了。
function maxProfit(prices: number[]): number {
let result = 0;
for (let i = 0; i < prices.length; i++) {
for (let j = i + 1; j < prices.length; j++) {
result = Math.max(result, prices[j] - prices[i]);
}
}
return result;
};当然直接提交会造成超时
贪心
题目要求查找最大收益，根据贪心思想，只要在每次寻找的过程中记录下最小股价和最大收益，不断更新得到最终结果。具体的处理方法如下：
从第二天开始遍历股价数组，判断每一天是否是最小的股价，如果是，那么将它记录下来作为当前的买入价。
每一天都计算以当前股价卖出时的最大收益，并将这个最大收益和之前计算得到的最大收益做比较，如果当前的最大收益比之前的最大收益要大，那么记录下来作为新的最大收益。
最终返回最大收益。
function maxProfit(prices: number[]): number {
let minPrice = Infinity;
let maxProfit = 0;
for (let i = 0; i < prices.length; i++) {
if (prices[i] < minPrice) {
minPrice = prices[i];
} else if (prices[i] - minPrice > maxProfit) {
maxProfit = prices[i] - minPrice;
}
}
return maxProfit;
};动态规划是不是最好的解答呢？
买卖股票的最佳时机含手续费
每次交易要支付手续费，只要把手续费从利润中减去即可，改写方程：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]) dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i] - fee)
解释：相当于买入股票的价格升高了。
在第一个式子里减也是一样的，相当于卖出股票的价格减小了。
注：如果直接把 fee 放在第一个式子里减，会有一些测试用例无法通过，错误原因是整型溢出而不是思路问题。一种解决方案是把代码中的 int 类型都改成 long 类型，避免 int 的整型溢出。
直接翻译成代码，注意状态转移方程改变后 base case 也要做出对应改变：
var maxProfit_with_fee = function(prices, fee) {
var n = prices.length;
var dp = new Array(n);
for (var i = 0; i < n; i++) {
dp[i] = new Array(2);
if (i - 1 == -1) {
// 初始状态
dp[i][0] = 0;
dp[i][1] = -prices[i] - fee;
// dp[i][1]
// = max(dp[i - 1][1], dp[i - 1][0] - prices[i] - fee)
// = max(dp[-1][1], dp[-1][0] - prices[i] - fee)
// = max(-inf, 0 - prices[i] - fee)
// = -prices[i] - fee
continue;
}
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i] - fee);
}
return dp[n - 1][0];
};空间优化：
var maxProfit_with_fee_2 = function(prices, fee) {
var n = prices.length;
var dp_i_0 = 0, dp_i_1 = Number.MIN_VALUE;
for (var i = 0; i < n; i++) {
var temp = dp_i_0;
dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
dp_i_1 = Math.max(dp_i_1, temp - prices[i] - fee);
}
return dp_i_0;
};可以参考 https://programmercarl.com/0309.最佳买卖股票时机含冷冻期.html
买卖股票的最佳时机 III
k = 2 和前面题目的情况稍微不同，因为上面的情况都和 k 的关系不太大：要么 k 是正无穷，状态转移和 k 没关系了；要么 k = 1，跟 k = 0 这个 base case 挨得近，最后也没有存在感。
这道题 k = 2 和后面要讲的 k 是任意正整数的情况中，对 k 的处理就凸显出来了，我们直接写代码，边写边分析原因。
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]) dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
原始的状态转移方程，没有可化简的地方
但按照之前的代码，我们可能想当然这样写代码（错误的）：
var k = 2;
var dp = new Array(n);
for (var i = 0; i < n; i++) {
dp[i] = new Array(k + 1);
for (var j = 0; j < k + 1; j++) {
dp[i][j] = new Array(2);
}
if (i - 1 == -1) {
// 处理 base case
dp[i][k][0] = 0;
dp[i][k][1] = -prices[i];
continue;
}
dp[i][k][0] = Math.max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
}
return dp[n - 1][k][0];为什么错误？我这不是照着状态转移方程写的吗？
还记得前面总结的「穷举框架」吗？就是说我们必须穷举所有状态。其实我们之前的解法，都在穷举所有状态，只是之前的题目中 k 都被化简掉了。
比如说第一题，k = 1 时的代码框架：
var n = prices.length;
var dp = Array.from({ length: n }, () => new Array(2).fill(0));
for (var i = 0; i < n; i++) {
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] + prices[i]);
dp[i][1] = Math.max(dp[i-1][1], -prices[i]);
}
return dp[n - 1][0];但当 k = 2 时，由于没有消掉 k 的影响，所以必须要对 k 进行穷举：
var maxProfit_k_2 = function(prices) {
var max_k = 2, n = prices.length;
var dp = new Array(n).fill(0).map(()=>new Array(max_k+1).fill(0).map(()=>new Array(2).fill(0)));
for (var i = 0; i < n; i++) {
for (var k = max_k; k >= 1; k--) {
if (i - 1 == -1) {
// 处理 base case
dp[i][k][0] = 0;
dp[i][k][1] = -prices[i];
continue;
}
dp[i][k][0] = Math.max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
}
}
// 穷举了 n × max_k × 2 个状态，正确。
return dp[n - 1][max_k][0];
};注：这里肯定会有读者疑惑，k 的 base case 是 0，按理说应该从 k = 1, k++ 这样穷举状态 k 才对？而且如果你真的这样从小到大遍历 k，提交发现也是可以的。
这个疑问很正确，因为我们前文 动态规划答疑篇 有介绍 dp 数组的遍历顺序是怎么确定的，主要是根据 base case，以 base case 为起点，逐步向结果靠近。
但为什么我从大到小遍历 k 也可以正确提交呢？因为你注意看，dp[i][k][..] 不会依赖 dp[i][k - 1][..]，而是依赖 dp[i - 1][k - 1][..]，而 dp[i - 1][..][..]，都是已经计算出来的，所以不管你是 k = max_k, k--，还是 k = 1, k++，都是可以得出正确答案的。
那为什么我使用 k = max_k, k-- 的方式呢？因为这样符合语义：
你买股票，初始的「状态」是什么？应该是从第 0 天开始，而且还没有进行过买卖，所以最大交易次数限制 k 应该是 max_k；而随着「状态」的推移，你会进行交易，那么交易次数上限 k 应该不断减少，这样一想，k = max_k, k-- 的方式是比较合乎实际场景的。
当然，这里 k 取值范围比较小，所以也可以不用 for 循环，直接把 k = 1 和 2 的情况全部列举出来也可以：
/**
* 状态转移方程：
* dp[i][2][0] = max(dp[i-1][2][0], dp[i-1][2][1] + prices[i])
* dp[i][2][1] = max(dp[i-1][2][1], dp[i-1][1][0] - prices[i])
* dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1] + prices[i])
* dp[i][1][1] = max(dp[i-1][1][1], -prices[i])
*
* 空间复杂度优化版本
*/var maxProfit_k_2 = function(prices) {
let dp_i10 = 0, dp_i11 = -Infinity;
let dp_i20 = 0, dp_i21 = -Infinity;
for (let price of prices) {
dp_i20 = Math.max(dp_i20, dp_i21 + price);
dp_i21 = Math.max(dp_i21, dp_i10 - price);
dp_i10 = Math.max(dp_i10, dp_i11 + price);
dp_i11 = Math.max(dp_i11, -price);
}
return dp_i20;}有状态转移方程和含义明确的变量名指导，相信你很容易看懂。其实我们可以故弄玄虚，把上述四个变量换成 a, b, c, d。这样当别人看到你的代码时就会大惊失色，对你肃然起敬。
买卖股票的最佳时机 IV
有了上一题 k = 2 的铺垫，这题应该和上一题的第一个解法没啥区别，你把上一题的 k = 2 换成题目输入的 k 就行了。
但试一下发现会出一个内存超限的错误，原来是传入的 k 值会非常大，dp 数组太大了。那么现在想想，交易次数 k 最多有多大呢？
一次交易由买入和卖出构成，至少需要两天。所以说有效的限制 k 应该不超过 n/2，如果超过，就没有约束作用了，相当于 k 没有限制的情况，而这种情况是之前解决过的。
所以我们可以直接把之前的代码重用：
var maxProfit_k_any = function(max_k, prices) {
var n = prices.length;
if (n <= 0) {
return 0;
}
if (max_k > Math.floor(n / 2)) {
// 复用之前交易次数 k 没有限制的情况
return maxProfit_k_inf(prices);
}
// base case：
// dp[-1][...][0] = dp[...][0][0] = 0
// dp[-1][...][1] = dp[...][0][1] = -infinity
var dp = Array(n).fill(null).map(() => Array(max_k + 1).fill(null).map(() => [0, 0]));
// k = 0 时的 base case
for (var i = 0; i < n; i++) {
dp[i][0][1] = -Number.MAX_VALUE;
dp[i][0][0] = 0;
}
for (var i = 0; i < n; i++) {
for (var k = max_k; k >= 1; k--) {
if (i - 1 === -1) {
// 处理 i = -1 时的 base case
dp[i][k][0] = 0;
dp[i][k][1] = -prices[i];
continue;
}
dp[i][k][0] = Math.max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
}
}
return dp[n - 1][max_k][0];
};至此，6 道题目通过一个状态转移方程全部解决。
参考文章：
一个方法团灭 LeetCode 股票买卖问题 https://labuladong.online/algo/dynamic-programming/stock-problem-summary/
https://programmercarl.com/0121.买卖股票的最佳时机.html
LeetCode：121.买卖股票的最佳时机 & II——动态规划 https://developer.aliyun.com/article/1198663
转载本站文章《DP笔记(13)：区间DP——买卖股票问题》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/leetcode/9135.html