[!info] related notes 算法面试题型 MOC 动态规划 分割等和子集 零钱兑换 零钱兑换 II 目标和

背包 DP

一句话

从若干物品中做选择，满足某种容量限制，求最优值 / 方案数 / 是否可行。

一页式速查表

类型	是否可重复选	常见状态	枚举顺序	代表题
01 背包最值	否	dp[j] / dp[i][j]	容量倒序	[[partition-equal-subset-sum	分割等和子集]]
完全背包最值	是	dp[j] / dp[i][j]	容量正序	[[coin-change	零钱兑换]]
完全背包方案数	是	dp[j]	物品外层、容量正序	[[coin-change-ii	零钱兑换 II]]
01 背包方案数	否	dp[j]	容量倒序	[[target-sum	目标和]]
恰好装可行性	视题而定	dp[j] = bool	看题型	[[partition-equal-subset-sum	分割等和子集]]

识别信号

• 给你一堆物品，每个物品有“体积 / 重量 / 代价”
• 有容量限制、目标和、预算限制
• 每个物品最多用一次 / 可以无限次使用

01 背包

每个物品最多选一次。

状态

dp[i][j] = 从前 i 个物品中选，容量不超过 j 时的最优值 / 方案数

转移

• 不选第 i 个：dp[i - 1][j]
• 选第 i 个：dp[i - 1][j - w[i]] + v[i]

最优值型：

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])

一维优化模板

for (let i = 0; i < n; i++) {
    for (let j = m; j >= w[i]; j--) {
        dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
    }
}

倒序原因：防止同一轮里同一个物品被重复使用。

完全背包

每个物品可以选无限次。

转移

因为选了当前物品后还能继续选它，所以来自当前行：

dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + v[i])

一维优化模板

for (let i = 0; i < n; i++) {
    for (let j = w[i]; j <= m; j++) {
        dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
    }
}

正序原因：允许当前物品在同一轮被重复使用。

三种高频问法

1. 至多装

不要求刚好装满。

2. 恰好装

必须刚好凑出目标。

初始化往往是关键：

• 最大值型：dp[0] = 0，其他设 -INF
• 最小值型：dp[0] = 0，其他设 INF
• 可行性：dp[0] = true

3. 至少装

达到至少某个值即可。常见做法是最后枚举 j >= target。

样例 1：分割等和子集（01 背包可行性）

题目：分割等和子集

题意：数组能不能选出一些数，使其和等于总和的一半。

状态

dp[j] 表示是否能恰好凑出和 j。

转移

dp[j] = dp[j] || dp[j - nums[i]]

容量倒序枚举，因为每个数只能用一次。

样例 2：零钱兑换（完全背包最小值）

题目：零钱兑换

题意：硬币可重复使用，问凑成金额 amount 的最少硬币数。

状态

dp[j] 表示凑出金额 j 的最少硬币数。

转移

dp[j] = min(dp[j], dp[j - coin] + 1)

容量正序，因为硬币能重复使用。

高频坑

• 01 背包和完全背包把顺序写反
• 不清楚状态里存的是最值、方案数还是可行性
• 恰好装题目初始化乱写，导致不可达状态参与转移
• 组合和排列搞混：枚举物品在外还是枚举容量在外，含义不同

模板与代表题

• 模板：01 背包模板、完全背包模板
• 代表题：分割等和子集、零钱兑换、零钱兑换 II、目标和