0xlightyear
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]) 想了很久想不通，望大佬解惑
我有点想明白了。 ``` 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]
@labuladong 是的是的！无论是从"我希望不超过k次买卖"还是"不允许超过k次买卖"，两个角度描述的核心都是"不超过k次"的最值。同一个意思。想了一天终于明白了。非常感谢博主做出这一套教程，思路太棒了！
@luckywords 我感觉你的解法和东哥那个遍历数字解法本质是一样的。你尝试对nums排序了吗？
visited 和 onPath 这两个变量是否有些重复？
不重复，这两个变量很有必要，目的不一样。visited可以减少很大一部分计算量
将Union find这个算法描述成等价关系太精彩了。 Union find利用根节点，巧妙的实现了自反性，对称性和传递性。 生活中除了等价关系还有一类比较常见的关系，偏序关系(自反性，反对称性，传递性)。请问有人了解偏序关系应该用什么算法处理？或者是否能在UF上做修改，使其适用于偏序关系呢？