算法►动态规划

DP 模型：从回溯语义到 0-1 背包与完全背包（2026-01-13）

本文通过 494、322、2915 三道典型题目，总结 0-1 背包与完全背包的统一建模方式。重点在于如何从回溯语义自然推导出动态规划模型。

基础题目：01背包、完全背包

01背包变形：

494.目标和、2915.和为目标值的最长子序列的长度

完全背包变形：

322.零钱兑换

一、为什么要从“回溯语义”入手理解 DP？

在学习动态规划的过程中，我一度陷入这样的问题：

  • 明明知道这是 DP 题
  • 但一到写 dp[i][j] 就容易：
    • 不知道从何下手
    • 理解错误状态含义
    • 写错初始化

后来我解题循序渐进旨在加深对回溯与DP的理解：

所有 DP 题，先用 dfs(i, j) 把“语义”想清楚，再翻译成 DP。

这篇博客正是围绕这一方法，总结 0-1 背包与完全背包 这两类最常见的 DP 模型。

二、统一视角：什么是“背包模型”？

从抽象层面看，背包问题的本质只有一句话：

枚举每个输入元素，决定“选或不选”，并维护一个容量约束。

0-1 背包模型

问题描述

  • 有 n 个物品
  • 第 i 个物品体积 w[i]，价值 v[i]
  • 每个物品最多选一次
  • 在容量 capacity 内，求最大价值和

回溯语义三问（非常重要）

  • 当前操作：枚举第 i 个物品选或不选：不选，剩余容量不变；选，容量减少 w[i]
  • 子问题：剩余容量为 c 时，前 i 个物品中的最大价值和
  • 下一个子问题：分类讨论：
    • 当前操作不选：剩余容量 c 从前 i-1 个物品中得到的最大价值
    • 当前操作选：剩余容量 c - w[i] 从前 i-1 个物品得到的最大价值

回溯表达式

1
2
3
4
5
6
7
8
9
10
int dfs(int i, int c, int[] w, int[] v) {
    if (i < 0) return 0;
    if (w[i] > c) {
        return dfs(i - 1, c, w, v);
    }
    return Math.max(
        dfs(i - 1, c, w, v),                 // 不选
        dfs(i - 1, c - w[i], w, v) + v[i]    // 选
    );
}

一旦写出这段递归，DP 就已经成功了一半。

完全背包模型

完全背包与 0-1 背包只有一个本质区别：

当前物品是否允许在同一层决策中被再次使用

回溯表达式

1
2
3
4
dfs(i, c) = max(
    dfs(i - 1, c),          // 不选
    dfs(i, c - w[i]) + v[i] // 选，并且还能继续选 i
)

一个非常容易困惑的问题

为什么不需要写 dfs(i - 1, c - w[i])？即选了一次后不在选了

原因在于：

  • dfs(i, c - w[i]) 中，下一层仍然可以选择“不选”，自然会递归到 dfs(i - 1, c - w[i])

也就是说：

“选一次就不再选”这个语义，已经被递归本身隐式表达了。

这是我在完全背包中收获最大的一个认知点。

三、常见背包问题的分类方式

在做题时，我会优先判断两个维度：

1. 装不装满？

  • 至多装 capacity
  • 恰好装 capacity
  • 至少装 capacity

2. 求什么？

  • 方案数
  • 最大价值
  • 最小价值

大部分 LeetCode 背包题，都可以被放入这个二维分类表中。

四、结合具体题目分析

494. 目标和 —— 0-1 背包（恰好装满，求方案数）

建模思路

  • 每个数只能用一次 → 0-1 背包
  • 每个数选或不选 → 枚举符号
  • 本质是：恰好凑出 target 的方案数

回溯语义

1
dfs(i, t)：使用前 i 个数，凑出和为 t 的方案数

转移关系

1
2
dfs(i, t) = dfs(i - 1, t)           // 不选 nums[i]
          + dfs(i - 1, t - nums[i]) // 选 nums[i]

在实现时，我采用了：

  1. 回溯 + 记忆化搜索
  2. 翻译为二维 DP
  3. 再做空间优化

这道题让我深刻体会到：
dp[i][j] 的含义，必须和 dfs(i, j) 的返回值一一对应。

322. 零钱兑换 —— 完全背包（恰好装满，求最小价值）

模型映射

零钱兑换 背包模型
amount capacity
coin 面值 物品体积
使用枚数 价值（每次 +1）

为什么是完全背包？

因为：同一种硬币，在同一轮决策中可以被重复使用

转移方程（核心）—— 经过回溯、空间优化的结果

1
2
3
4
dp[j] = min(
    dp[j],              // 不使用当前硬币
    dp[j - coin] + 1    // 使用一次当前硬币
)

2915. 和为目标值的最长子序列 —— 0-1 背包（恰好装满，求最大价值）

抽象方式

  • 每个元素只能选一次 → 0-1 背包
  • nums[i] 作为“体积”
  • 每选一个元素，价值 +1

语义定义

1
dp[j]：和为 j 时，能得到的最大长度

这道题让我意识到：

“价值”不一定是题目直接给的，而可以从题目中转化。

五、空间优化：理解即可，不必强求

在这三道题中，状态转移均只依赖于：

  • 上一层 i - 1
  • 或当前层更小的 j

因此可以：

  1. dp[n][target] → dp[2][target]
  2. 再进一步压缩为一维数组

但我目前的态度是：

空间优化属于锦上添花，优先保证语义正确。

如果一维 DP 的依赖方向一时想不清楚，我会选择保留二维。

六、总结与反思

通过这几道题，我对动态规划的理解有了一个明显转变：

  • DP 的核心不在公式
  • 而在 状态含义 + 转移语义

我目前仍然习惯：先写 dfs(i, j)，再翻译成 dp

但我也希望，随着练习的增多，能够逐渐做到：

  • 直接从问题 → 状态定义 → 转移方程
  • 减少对回溯的依赖

这是我接下来刻意训练的方向。

相关代码

本文涉及的所有代码与笔记，均已同步至我的 GitHub 算法仓库，作为 Java 后端校招过程中的学习记录。