一个方法团灭 LeetCode 股票买卖问题 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：一个方法团灭 LeetCode 股票买卖问题

评论礼仪 见这里，违者直接拉黑。

[MrXIAGAO]

感谢分享，思路很清晰，公式很强大！
但是似乎并不是【max_k】才是结果：例如价格持续走低，一笔交易都不做的情况。

[restart365]

最困难的是理解K这个维度到底是什么

[CarlLy7]

你可能理解错了吧，max_k只是表明一共可以进行多少次交易

[zhangmuwuge]

max_k的意思是 最多进行max_k次交易能得到的收益,如果价格持续走低,那其实就是 k= 0的时候最大,这个k=0的结果会根据转移方程一直转移到 max_k 中

[keeleys]

dp[i][1] = max(dp[i-1][1], -prices[i])

-prices[i]怎么理解呢

[miiiiiko]

今天之前不做交易，因此历史收益是0，今天第一次买入股票，花费prices[i], 0-prices[i]

[ghost]

-prices[i] 我理解，第一天你如果持有，那么你就是第一天买入了股票，此时你的利润就是 - prices[i]

[ZhongkangLi]

-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]。

[gostudying]

因为该题只允许交易一次，所以买入即为第一次买入，也就是前面的利润dp[i-1][0]=0

[20183501053lxc]

文中的“而且注意 k 的限制，我们在选择 buy 的时候，把 k 减小了 1，很好理解吧，当然你也可以在 sell 的时候减 1，一样的。”这句话应该是只有买入的时候才能够减1吧，卖出的时候不能减1。因为只有买入之后才能够卖出吧？而且我在写188.买卖股票的最佳时机 IV（困难）时候，buy操作减1是能够过题，但是sell操作减1是不能够过样例的。

[NathanSu0304]

冷冻期的那个题，i-2 越界到-1是怎么处理的呢？ 不是太通透？

[derainzhou]

我觉得可以这么理解;

// 第一情况: 今天持有股票, 昨天就可能持有了, 收益 = dp(memo, prices, i - 1, 1)
// 第二种情况: 由于冷冻期的存在, 最小间隔的买卖是在前天(前天卖出股票了), 昨天是冷冻期今天买入, 收益 = dp(memo, prices, i - 2, 0) - prices[i]
// 为什么是选最小间隔呢? 既然我们站在未来, 那么每次买卖肯定是赚钱的, 更多的交易次数意味着收益更高
res = Math.max(dp(memo, prices, i - 1, 1), dp(memo, prices, i - 2, 0) - prices[i]);

[derainzhou]

我理解股票问题都是在每天做选择, 今天交易利益最大化, 还是不交易利益最大化;

[derainzhou]

选择最小间隔, 才不会漏掉某些情况;

[derainzhou]

不好意思, 回复错了, 应该是回复LilyLoveLife, 这个老哥的[题目三，冷冻期的， dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i])怎么理解？].

网络不行, 一刷新位置都变了

[labuladong]

@20183501053lxc 你说的有道理，我在文中重新探讨了这个问题

[labuladong]

@NathanSu0304 我重新修改了一下

[xiaomudan778]

感谢分享，爆赞 [强]

[0xlightyear]

非常感谢！整体逻辑非常清晰。但是有一个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])
想了很久想不通，望大佬解惑

[0xlightyear]

我有点想明白了。

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]

[zhangmuwuge]

k的意思是 最多进行k次交易,假如k=5, dp[i][5][x] 意思是 最多进行5次交易的利润,这个时候你可以交易0次 1次 2次 3次 4次 5次 ,但是价格数组可能是多种顺序,所以这里并不是说交易次数越多利润越多 (比如价格是降序的时候,还不如不买卖呢,买卖必亏)

[rasasayang]

dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]) ,这里面，今天买了，对于昨天来说不应该是k+ 1嘛？，今天买完还有k次，昨天应该有k+1次啊。不是很理解这个地方。

[labuladong]

@0xlightyear 很高兴你提出这个问题，不过我觉得你的理解有点偏差。其实很好理解，k 的定义是允许买卖的次数上限，那么如果这个上限规定为 0，相当于完全不准你买入和卖出，所以利润一定是 0。就好比你去炒股，结果号被封了，就算你能预知未来，但人家根本不让你入场，你还是赚不到钱。

[DarkFlameMasterDev]

1. 有一个地方不明白，在 一、穷举框架 里

我们想求的最终答案是 dp[n - 1][K][0]，即最后一天，最多允许 K 次交易，最多获得多少利润。

这里用的是 大写 K，但是 0 <= k <= K , dp 里面存储的应该是 dp[i][k][0 or 1]，猜测是写错了

2. 还有一个不明白的地方：为什么 base case dp[...][0][0] = 0
   k表示当前交易的最大限制，那么 当前交易的最大限制，也就是现在剩余的可交易次数
   也就是说 dp[i][k][0 or 1] 在不断穷举的时候，k 是会 减小的
   dp[0][3][0] -> dp [9][0][0]，dp[9][0][0]=0 ?

看了 0xlightyear 的评论，但是东哥没解释

这个时候的利润为何不能是最后一笔卖出的利润？
dp[i][0][0] = max(dp[i-1][0][0], dp[i-1][0][1]+price[i])
想了很久想不通，望大佬解惑

包括

那么如果这个上限规定为 0，相当于完全不准你买入和卖出

这个我也能理解，但是 大写K 是规定好的，k应该是随着 穷举 变化的

[DarkFlameMasterDev]

现在懂了，看看自己的评论感觉好丢脸

[DarkFlameMasterDev]

比如说 dp[3][2][1] 的含义就是：今天是第三天，我现在手上持有着股票，至今最多进行 2 次交易。
这句话是我疑惑的原因，尤其是 至今最多进行 2 次交易，给我一种假如第三天交易了一次，那么第四天k就会减一 的感觉，尤其是这个至今更让我迷惑了
应该改成，dp[3][2][1] 的含义就是：在最多限制2次交易的情况下，第三天手里持有股票
这样就明确了在一个时间线里，k 也就是dp的第二个下标是不变的
而dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])之所以会有k-1，是因为k-1 是另一个时间线的，并不指的是k会随着天数不断下降

[0xlightyear]

@labuladong 是的是的！无论是从"我希望不超过k次买卖"还是"不允许超过k次买卖"，两个角度描述的核心都是"不超过k次"的最值。同一个意思。想了一天终于明白了。非常感谢博主做出这一套教程，思路太棒了！

[labuladong]

@0xlightyear 加油~

[changchingchi]

寫的真的是很好 謝謝！

[asdfczy]

对于这个case，我最开始也是很疑惑的，我认为应该是：

dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k+1][0] - prices[i])

因为直觉上认为昨天的交易次数上限肯定是比今天多才行，但是仔细想想这是不可能的。

后面想通了，这个k应该这样来理解：
截止到今天交易次数上限为k，注意是截止到今天，今天是包含了昨天的，昨天的交易次数上限必定小于等于今天的交易次数上限，而我今天要进行1次交易（买入），所以留给昨天交易上限只能是k-1了。

注意交易的定义：文中定义是我们把一次买入和一次卖出定义为一次「交易」。因为我们必须先买入才可能卖出，所以当进行一次买入操作相当于隐形的包含后面一次卖出，所以在代码实现时，交易次数的减1操作可以认为是买入的时候进行，卖出的时候不影响交易次数。

[labuladong]

是的，可以举个具体的例子：比方说要求你的银行卡里今天至少有 100 块钱，且你确定你今天可以赚 10 块钱，那么你就要保证昨天的银行卡要至少剩下 90 块钱。

[zhangmuwuge]

其实我感觉 k还是从0开始循环比较好......毕竟最大交易次数递增的时候,利润是可能增加的

[leihehehe]

关于k的含义，我说说自己的理解。注意这里的k表示的是【最多可以完成的交易次数】
如果我今天持有股票，那么我们要得到的是：dp[i][k][1]，dp[i][k][1]表示的是在第i天结束，最多可以交易k次，且我持有股票的情况下，这个时候的最大利益。
因此有两种情况：

1. 我昨天就已经持有股票了，今天实际上什么也没做 dp[i-1][k][1]
2. 我昨天还没持有股票，股票是今天买的 dp[i-1][k-1][0] - prices[i]

在第二种情况中，这里为什么k-1呢？

因为第二种情况中我确定【今天买了股票】，因此我们需要保证之前几天的交易不会把【最大交易次数k】给用完，不然用完了，今天肯定买不了了，所以在之前的天数里，最多只能有k-1 次最大交易次数，以便在第 i 天（今天）买入股票，

[sendon1982]

#121题，为什么按照框架会有错误

        for (int 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]);  // 必须 Math.max(dp[i - 1][1], 0 - prices[i]); 才能通过
        }

[zhangmuwuge]

因为只能买卖一次. 所以当某一天持有股票的时候,肯定是当天买入

[shiboys]

屌爆了！

[masteroffan]

123 // 穷举了 n × max_k × 2 个状态，正确。
return dp[n - 1][max_k][0];
返回值这边，为什么是max_k呀，不是很理解

[wuzeyu2015]

求教，第三个版本的k=2的股票交易，为什么用for循环的dp可以通过，但是递归+剪枝的dp就要超时呢，感觉复杂度应该是一样的呀

var memo map[string]int
func maxProfit(prices []int) int {
    memo = make(map[string]int)
    return profit(prices, len(prices)-1, 2, 0)
}


func profit(prices []int, i, j int, state int) int {
    key := fmt.Sprintf("%d_%d_%d", i,j,state)
    if i == 0 || j == 0 {
        if state == 0 {
            return 0
        } else {
            return -prices[0]
        }
    }
    if _, ok := memo[key]; ok {
        return memo[key]
    }
    if state == 0 {
        memo[key] = max(profit(prices, i-1,j,0), profit(prices, i-1,j,1)+prices[i])
        return memo[key]
    } else {
        memo[key] = max(profit(prices, i-1,j,1), profit(prices, i-1,j-1,0)-prices[i])
        return memo[key]
    }
}

func max(a, b int) int {
    if a < b {
        return b
    }
    return a
}```

[wnykuang]

疑似勘误：

但为什么我从大到小遍历 k 也可以正确提交呢？

应该是：

但为什么我从小到大遍历 k 也可以正确提交呢？

[lichever]

贴下代码看看？我猜 你k的定义变了

[DreamYuki]

谢谢分享

[paiky]

121和122的优化空间后的temp似乎可以不需要？我看可以跑过去

[zhucoffee]

注意123题，c++的同学不要用la老师给的动态变长数组定义dp，要用vector。否则过不了哈。

[Link-GZJ]

购买次数限制为K时，下面这块代码没必要写吧，因为dp[i][0][1] 这种情况根本不存在(程序不会用到)，dp[i][0][0] 本来就是0
// k = 0 时的 base case
for (int i = 0; i < n; i++) {
dp[i][0][1] = Integer.MIN_VALUE;
dp[i][0][0] = 0;
}

[lzh2580]

这是来自QQ邮箱的假期自动回复邮件。   您好，我最近正在休假中，无法亲自回复您的邮件。我将在假期结束后，尽快给您回复。

[labraka]

英文高赞题解没了QAQ

[CZT0]

这里四个状态的顺序有没有影响，我测试了下顺序任意顺序答案都正确

func maxProfit_k_2(prices []int) int {
    // 初始化 base case
    dp_i10, dp_i11 := 0, math.MinInt64
    dp_i20, dp_i21 := 0, math.MinInt64
    for _, price := range prices {
        dp_i20 = max(dp_i20, dp_i21+price)
        dp_i21 = max(dp_i21, dp_i10-price)
        dp_i10 = max(dp_i10, dp_i11+price)
        dp_i11 = max(dp_i11, -price)
    }
    return dp_i20
}

[codezs09]

有影响啊。 不信你试试先更新 dp_i11， 它的值变了会影响其他变量的更新