算法学习记录17——力扣“股票系列题型”

不涉及题目讲解，只介绍题目中容易踩的坑！！！

1、dp[j][0]和dp[j][1]的更新顺序为什么没要求？

2、为什么最多 k 次交易的股票 DP 不需要对 k倒序遍历？

一、先明确 DP 的定义（这是一切的前提）

代码中 DP 的含义是：

dp[j][0]：在「最多 j 次交易」的限制下，不持股的最大利润 dp[j][1]：在「最多 j 次交易」的限制下，持股的最大利润

⚠️ 关键在于这四个字：

最多 j 次交易

而不是「已经完成 j 次交易」。

这是后面所有结论的根源。

二、状态转移回顾

每天价格为price，转移方程是：

dp[j][1]=max(dp[j-1][0]-price,# 今天买入dp[j][1]# 之前就持有)dp[j][0]=max(dp[j][1]+price,# 今天卖出dp[j][0]# 之前就不持有)

这里有两个看起来“危险”的点：

1. dp[j][1]用到了dp[j-1][0]
2. dp[j][0]又用到了本轮更新后的dp[j][1]

按很多 DP 的经验，这似乎会导致状态污染。

但实际上不会。

三、第一个疑问：本轮dp[j][1]被dp[j][0]使用，安全吗？

假设dp[j][1]是刚更新的：

dp[j][1]=dp[j-1][0]-price

那么dp[j][0]中的这一项就是：

dp[j][1]+price=(dp[j-1][0]-price)+price=dp[j-1][0]

这意味着什么？

👉同一天买入 + 同一天卖出 = 什么都没做

• 利润不会增加
• 交易次数也不会被“白嫖”

所以即便用了本轮的dp[j][1]，也只是一个无效操作，不会破坏结果。

四、核心原因：j 表示的是「最多」，不是「已经用掉」

这是最重要的一点。

1️⃣ 如果 j 表示「已经完成 j 次交易」

那么：

• dp[j]一定严格依赖dp[j-1]
• 正序遍历会让一次交易被重复使用
• 必须倒序

这就和 0/1 背包是完全一致的。

2️⃣ 但这道题里，j 表示「最多 j 次交易」

这意味着：

dp[j] ≥ dp[j-1]

• 多给一次交易额度，只会让解更好或不变
• 用到「本轮更新的 dp[j-1]」依然是合法状态

👉 不存在“交易次数被重复消费”的问题。

五、为什么正序遍历不会“超额交易”？

假设我们正序遍历：

j = 1 → 2 → 3

当我们计算dp[2]时：

• 用到的dp[1]表示的是：

  • 在当前天结束时，最多 1 次交易的最优状态

用这个状态再买一次：

• 得到的是「最多 2 次交易」
• ✔ 完全合法

而不是：

• “已经完成 1 次交易，再偷偷多用一次”

六、和「必须倒序」的股票 DP 对比

如果我们把定义改成：

dp[j][0]：已经完成 j 次交易，不持股 dp[j][1]：已经完成 j 次交易，持股

那么转移会变成：

dp[j][1]=max(dp[j][1],dp[j][0]-price)dp[j][0]=max(dp[j][0],dp[j][1]+price)

此时：

• dp[j]依赖dp[j]
• 正序遍历一定出错
• 必须倒序遍历 j

👉 是否倒序，完全取决于 j 的语义，而不是题目是不是“股票”。

七、总结（给以后的自己）

是否需要对 k 倒序遍历，关键不在于 DP 的形式，
而在于 j 表示什么。

再补一句非常重要的经验：

在「最多 k 次交易」的股票 DP 中，
即便同一天发生“买入 → 卖出”，
也只会产生 0 利润，不会破坏状态。