dp回溯简记
2026-04-01 11:57:59
发布于：北京
1阅读
0回复
0点赞
你的总结非常接近核心逻辑，但可以再补充一些细节和边界情况，让这个结论更严谨。
对于大部分线性 DP 问题（比如打家劫舍、0-1 背包、最长上升子序列等），回溯方案的核心确实是：
从最终状态倒推，通过比较当前 dp 值和「转移来源的 dp 值」是否相等，判断是否选择了当前项；最后将结果逆序，得到正序方案。
但要注意几个关键前提和例外情况：
一、 这个规律成立的核心条件
状态转移方程是「选择型」的
线性 DP 的状态 dp[i] 通常对应两种选择：
选第 i 项：dp[i] = dp[prev_i] + val[i]
不选第 i 项：dp[i] = dp[i-1]
回溯时，只要 dp[i] != dp[i-1]，就说明选了第 i 项，然后跳到 prev_i；否则没选，跳到 i-1。
这正是你说的「看 dp[i] 和上一项是否变化」。
状态转移的来源是确定的
比如打家劫舍的 dp[i] 来源只有两个：dp[i-1]（不选）、dp[i-2]+a[i]（选），来源明确，回溯时不会有歧义。
二、 需要注意的例外和细节
多来源转移的情况
有些线性 DP 的 dp[i] 可能有多个转移来源，这时不能只看和上一项是否相等。比如 完全背包：dp[j] = max(dp[j], dp[j-w[i]] + v[i])
回溯时，dp[j] 可能来自任意一个满足 j>=w[i] 且 dp[j] = dp[j-w[i]]+v[i] 的物品 i，这时需要遍历所有物品找来源，而不是只和 j-1 比较。
收益可为负的情况
比如我们刚做的星灯题，dp[i] 会取 max(dp[i-1], dp[i-2]+a[i])，但如果 a[i] 是负数，dp[i-2]+a[i] 可能小于 dp[i-1]，这时必然不选 i。
这种情况依然符合「变化则选」的规律，但要注意 dp 初始化时要考虑「不选任何项」的收益（比如星灯题的 dp[1] = max(0, a[1])）。
非「选 / 不选」类的线性 DP
比如 最长公共子序列（LCS），它的状态 dp[i][j] 表示字符串 A[1~i] 和 B[1~j] 的 LCS 长度，转移方程是：
若 A[i]==B[j]：dp[i][j] = dp[i-1][j-1]+1
否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])
回溯时，不是看和「上一项」的变化，而是看 dp[i][j] 等于哪个来源：
等于 dp[i-1][j-1]+1 → 选 A[i]，跳到 i-1,j-1
等于 dp[i-1][j] → 跳到 i-1,j
等于 dp[i][j-1] → 跳到 i,j-1
这类问题依然是「倒推找来源」，但「上一项」的定义变成了多维的状态来源。
三、 最终结论
可以修正为更严谨的表述：
对于选择型线性 DP 问题（选 / 不选当前项），回溯的核心是：
从最终状态 dp[n]（或 dp[n][m]）倒推；
比较当前 dp 值与所有可能的转移来源值；
若当前 dp 值来自「选当前项」的转移 → 记录当前项，跳到对应来源状态；
否则 → 跳到「不选当前项」的来源状态；
最后逆序输出记录的项，得到正序方案。
这里空空如也
有帮助，赞一个