labuladong
一个方法团灭 LeetCode 股票买卖问题 :: labuladong的算法小抄
-prices[I]只出现在k = 1的情况。因为如果只有一次交易的话，那每天的dp[i][1]状态（第i天手持股票）只会是因为我在当天购买了股票，使得我目前的资本为-prices[I]，所以是负数。 每天的dp[i][1]状态不会依赖于dp[i-1][0]， 也就是当k =1的时候dp[i][1] 不等于dp[i-1][0] - prices[I]。
文中的“而且注意 k 的限制，我们在选择 buy 的时候，把 k 减小了 1，很好理解吧，当然你也可以在 sell 的时候减 1，一样的。”这句话应该是只有买入的时候才能够减1吧，卖出的时候不能减1。因为只有买入之后才能够卖出吧？而且我在写188.买卖股票的最佳时机 IV（困难）时候，buy操作减1是能够过题，但是sell操作减1是不能够过样例的。
非常感谢！整体逻辑非常清晰。但是有一个Base case有点想不通。
dp[...][0][0] = 0
解释：因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0。
这个时候的利润为何不能是最后一笔卖出的利润？ dp[i][0][0] = max(~~dp[i-1][0][0]~~, dp[i-1][0][1]+price[i]) 想了很久想不通，望大佬解惑
我有点想明白了。
dp[...][0][0] = 0
解释：因为 k 是从 1 开始的，所以 k = 0 意味着根本不允许交易，这时候利润当然是 0。
比起说k=0意味着"根本不允许交易"， 对我来说k=0意味着"我不想交易" 更好理解一些。
dp[...][0][0] = 0的感觉是在我不知道股票走势的时候，我可以选择从头到尾不买不卖，这样我的利润一直是0，从而应对股票一直下跌的情况。
当然 dp[i][0][0] = max(dp[i-1][0][0], dp[i-1][0][1]+price[i])也是成立的，如果之前的在某种"状态"下的股票有盈利x，那我们的dp[...][0][0]在此状态之后，假设股票一直下跌，可以一直选择不买不卖，从而一直保持着x的盈利状态直至最后一天。如果有大于x的盈利，那么可以再更新dp[...][0][0]
@0xlightyear 很高兴你提出这个问题，不过我觉得你的理解有点偏差。其实很好理解，k 的定义是允许买卖的次数上限，那么如果这个上限规定为 0，相当于完全不准你买入和卖出，所以利润一定是 0。就好比你去炒股，结果号被封了，就算你能预知未来，但人家根本不让你入场，你还是赚不到钱。
@labuladong 是的是的！无论是从"我希望不超过k次买卖"还是"不允许超过k次买卖"，两个角度描述的核心都是"不超过k次"的最值。同一个意思。想了一天终于明白了。非常感谢博主做出这一套教程，思路太棒了！
@LilyLoveLife 第i天持有股票 可能是i-1天沒有進行買賣 或是 i-2 天前 (cooldown) 的profit來的. dp[i-2][0] 表示i-2天沒有股票然後現在買入-prices[i].
我昨天本没有持有，且截至昨天最大交易次数限制为 k - 1；但今天我选择 buy，所以今天我就持有股票了，最大交易次数限制为 k。
这个地方，今天 buy 了之后最大交易次数不是 -1 吗？那昨天不是应该是 k + 1 ？
请问第六题中为什么要初始化 k = 0 的 base case 呢？
for (int i = 0; i < n; i++) {
dp[i][0][1] = Integer.MIN_VALUE;
dp[i][0][0] = 0;
}
dp[i][0][1] 不会在dp中，dp[i][0][0] = 0 也会默认初始化 我试了下去掉这段代码也可以通过题目，不过去掉后执行时间慢了一倍
T[i][k][1] = max(T[i - 1][k][1], T[i - 1][k - 1][0] - prices[i])，交易次数减少不应该前面是k-1，后面是k吗，困扰了好久
第一题的改进版有个地方没想通、dp_i_1 = Integer.MIN_VALUE、这里我记得改进之前不是-price[i]么、也就是-price[0]、为啥变成负无穷了、
@MengyuanL dp_i_1用来存储买入的情况下的现金额。如果初次买入必然是负的买入价，即-price[i]。结合状态转移方程中使用Math.max()来传递最大利润，base case必须保证初始值必须总是小于任何的-price[i]。不然“贷款”买入股票的行为就不能在方程中转移。
我昨天本没有持有，且截至昨天最大交易次数限制为 k - 1；但今天我选择 buy，所以今天我就持有股票了，最大交易次数限制为 k 这是什么意思呀，交易一次，不是应该变成 k-2 吗
js 版本的各套算法
- 买卖股票的最佳时机（简单）k = 1
var maxProfit = function (prices) {
let n = prices.length;
let dp = new Array(n).fill(0).map(() => new Array(2).fill(0));
for (let i = 0; i < n; i++) {
if (i === 0) {
// 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], -prices[i]);
}
return dp[n - 1][0];
};
- 买卖股票的最佳时机 II（简单）k = +infinity
var maxProfit = function (prices) {
let n = prices.length;
let dp = new Array(n).fill(0).map(() => new Array(2).fill(0));
for (let i = 0; i < n; i++) {
if (i === 0) {
// 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];
};
- 买卖股票的最佳时机 III（困难）k = 2
var maxProfit = function (prices) {
let max_k = 2,
n = prices.length;
let dp = new Array(n).fill(0).map(
() => new Array(max_k + 1).fill(0).map(
() => new Array(2).fill(0)));
for (let i = 0; i < n; i++) {
for (let k = max_k; k > 0; k--) {
if (i === 0) {
// 处理 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];
};
- 买卖股票的最佳时机 IV（困难）k = any integer
var maxProfit = function (k, prices) {
let max_k = k,
n = prices.length;
if (n <= 0) return 0;
let dp = new Array(n).fill(0).map(
() => new Array(max_k + 1).fill(0).map(
() => new Array(2).fill(0)));
for (let i = 0; i < n; i++) {
for (let k = max_k; k > 0; k--) {
if (i === 0) {
// 处理 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 = +infinity with cooldown
var maxProfit = function(prices) {
let n = prices.length;
let dp = new Array(n).fill(0).map(() => new Array(2).fill(0));
for (let i = 0; i < n; i++) {
if (i === 0) {
// base case 1
dp[i][0] = 0;
dp[i][1] = -prices[i];
continue;
}
if (i === 1) {
// base case 2
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]);
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];
- 买卖股票的最佳时机含手续费（中等）k = +infinity with fee
var maxProfit = function(prices, fee) {
let n = prices.length;
let dp = new Array(n).fill(0).map(() => new Array(2).fill(0));
for (let i = 0; i < n; i++) {
if (i === 0) {
// base case 1
dp[i][0] = 0;
dp[i][1] = -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];
};
int maxProfit_k_any(int max_k, int[] prices) {
int n = prices.length;
if (n <= 0) {
return 0;
}
if (max_k > n / 2) {
// 交易次数 k 没有限制的情况
return maxProfit_k_inf(prices);
}
// base case：
// dp[-1][...][0] = dp[...][0][0] = 0
// dp[-1][...][1] = dp[...][0][1] = -infinity
int[][][] dp = new int[n][max_k + 1][2];
// k = 0 时的 base case
for (int i = 0; i < n; i++) {
dp[i][0][1] = Integer.MIN_VALUE;
dp[i][0][0] = 0;
}
for (int i = 0; i < n; i++)
for (int 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];
}
请教大佬，为什么最终取 max_k 呢？ 如果取 max_k, 计算 k 小于 max_k 场景的计算显得没啥意义。
