动态规划表法中正向/反向计算的选择策略与疑问

一、核心差异：遍历方向决定元素是否可重复使用 #

动态规划表法中，正向或反向遍历的本质是控制当前元素是否被允许重复参与状态转移，这直接决定了是否会出现重复计算：

以LeetCode 416. 分割等和子集（0-1背包问题）为例 #

该问题要求每个元素只能用一次，状态转移方程为：

f[subset_sum] = f[subset_sum] or f[subset_sum - num[i]] （当subset_sum >= num[i]时）

• 正向遍历的问题：
  代码实现：

  for num in nums:
      for i in range(0, len(dp)):
          if i >= num:
              dp[i] = dp[i - num] or dp[i]
  

  当输入为[2,2,3,5]时，处理第一个num=2会先将dp[2]更新为True；接着遍历到i=4时，会用到刚更新的dp[2]（已使用当前的2），相当于同一个元素被重复使用，最终错误地认为可以凑出和为6的子集（违反0-1背包“元素只能用一次”的规则）。
• 反向遍历的合理性：
  代码实现：

  for num in nums:
      for i in range(len(dp)-1, -1, -1):
          if i >= num:
              dp[i] = dp[i - num] or dp[i]
  return dp[-1]
  

  从大到小遍历时，计算dp[i]用到的dp[i-num]是未被当前num修改过的旧值，仅依赖之前处理过的元素，保证当前num只被使用一次，不会出现重复计算。

以LeetCode 279. 完全平方数（完全背包问题）为例 #

该问题允许平方数重复使用，正向遍历刚好契合需求：遍历过程中，计算dp[i]时可以用到当前轮次已更新的dp[i-num]，相当于允许重复使用当前的平方数，比如用1的平方数凑任意数值时，正向遍历能通过不断累加得到正确结果。

二、决策策略：从问题规则和状态依赖出发 #

推导完状态转移方程后，按以下步骤判断遍历方向：

• 明确背包类型
  • 0-1背包（元素只能用一次）：必须用反向遍历（从大到小），避免同一元素重复参与计算。
  • 完全背包（元素可重复使用）：必须用正向遍历（从小到大），允许同一元素多次参与计算。
• 拆解状态依赖关系
  • 如果dp[i]的更新需要依赖当前轮次已更新的dp值（允许重复用当前元素），选正向遍历。
  • 如果dp[i]的更新必须依赖当前轮次未更新的旧dp值（当前元素只能用一次），选反向遍历。
• 用小测试用例验证
  拿最小规模的测试用例手动跑两种遍历方式，比如416的[2,2,3,5]，正向遍历会错误返回True，反向遍历返回正确的False，快速验证遍历方向的正确性。

三、培养DP解题直觉的方法 #

• 先归类，再套模型：遇到DP问题先判断类型（背包类、最长子序列类、区间DP类等），背包类直接对应0-1/完全背包的遍历规则，减少决策成本。
• 手动推导状态表：不要急着写代码，拿小例子手动填写DP表，观察每一步状态的依赖来源——是来自上一轮的旧值，还是当前轮的新值，自然就能确定遍历方向。
• 对比相似问题：把同类型但规则不同的问题放在一起对比，比如416（0-1背包）和322. 零钱兑换（完全背包），分析遍历方向的差异和原因，强化记忆。
• 复盘错误案例：遇到遍历方向错误导致的bug，记录下错误原因（比如“416正向遍历导致同一元素重复使用”），下次遇到类似问题就能快速规避。

内容的提问来源于stack exchange，提问作者user30938231