Javajava算法
动态规划：01 背包与完全背包题型总结
总结了动态规划中的 01 背包与完全背包核心理论及典型题目。涵盖问题定义、通用解题框架、遍历顺序逻辑。通过目标和、分割等和子集详解 01 背包，通过最少硬币数、完全平方数、单词拆分详解完全背包。提供 Java 二维及一维 DP 实现，对比易错点与难点，帮助掌握状态转移与空间优化技巧。
总结了动态规划中的 01 背包与完全背包核心理论及典型题目。涵盖问题定义、通用解题框架、遍历顺序逻辑。通过目标和、分割等和子集详解 01 背包，通过最少硬币数、完全平方数、单词拆分详解完全背包。提供 Java 二维及一维 DP 实现，对比易错点与难点，帮助掌握状态转移与空间优化技巧。
背包问题是动态规划的经典分支，核心是「给定物品集合 + 目标容量，通过选择物品满足容量约束，求最优解（数量 / 最值 / 布尔值）」，主要分为两类：
| 背包类型 | 核心规则 | 适用场景 | 核心遍历逻辑 |
|---|---|---|---|
| 01 背包 | 每个物品只能选 1 次 | 目标和、分割等和子集 | 先物品 → 倒序遍历容量（防重复） |
| 完全背包 | 每个物品可重复选 | 最少硬币数、完全平方数 | 先物品 → 正序遍历容量（允重复） |
无论 01 / 完全背包，核心步骤一致，仅在「遍历顺序 / 转移细节」有差异：
问题转化：识别「物品」「容量」「优化目标」（方案数 / 最值 / 布尔值）；状态定义：
dp[i][j]（二维）= 考虑前i个物品，容量为j的最优解；dp[j]（一维）= 容量为j的最优解（空间优化）；初始化：确定基准状态（如dp[0][0]=1/dp[0]=0）；状态转移：基于「选 / 不选当前物品」推导；遍历顺序：按背包类型确定（01 倒序 / 完全正序）。
给定整数数组 nums 和目标值 target，给每个数加 + 或 -，求最终和为 target 的方案数。示例：nums=[1,1,1,1,1], target=3 → 输出 5。
设数组总和为 s，选部分数加 +（和为 p），另一部分加 -（和为 s-p）：p - (s-p) = target → 化简得 p = (target + s) / 2。问题转化为：从 nums 中选若干数（每个数只能选 1 次），和为 p 的方案数（01 背包）。
dp[i][j] = 考虑前 i 个数，凑和为 j 的方案数；dp[j] = 凑和为 j 的方案数（空间优化）。dp[0][0] = 1（无物品时，凑 0 的方案数 = 1），dp[0][j>0] = 0；dp[0] = 1（基准），其余默认 0。if (j >= nums[i-1]) {
// 选：dp[i-1][j-nums[i-1]] + 不选：dp[i-1][j]
dp[i][j] = dp[i-1][j] + dp[i-1][j - nums[i-1]];
} else {
dp[i][j] = dp[i-1][j]; // 不够选，只能不选
}
for (int num : nums) {
for (int j = p; j >= num; j--) {
dp[j] += dp[j - num]; // 选 + 不选的叠加
}
}
target 存总和，导致逻辑混乱（需单独用 s 存总和，p 存目标和）；(target+s) 是否为偶数、p 是否非负；dp[0]=1（基准丢失，结果全 0）。p 为负 / 总和小于 |target| 的特殊情况。class Solution {
public int findTargetSumWays(int[] nums, int target) {
// 1. 计算总和 + 合法性判断
int s = 0;
for (int num : nums) s += num;
if (Math.abs(target) > s || (target + s) % 2 != 0) return 0;
int p = (target + s) / 2;
if (p < 0) return 0;
// 2. 二维 DP 初始化
int n = nums.length;
int[][] dp = new int[n + 1][p + 1];
dp[0][0] = 1; // 基准
// 3. 状态转移
for (int i = 1; i <= n; i++) {
int num = nums[i - 1];
for (int j = 0; j <= p; j++) {
if (j >= num) {
dp[i][j] = dp[i-1][j] + dp[i-1][j - num];
} else {
dp[i][j] = dp[i-1][j];
}
}
}
return dp[n][p];
}
}
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int s = 0;
for (int num : nums) s += num;
if (Math.abs(target) > s || (target + s) % 2 != 0) return 0;
int p = (target + s) / 2;
if (p < 0) return 0;
int[] dp = new int[p + 1];
dp[0] = 1; // 基准
// 01 背包：先物品，后倒序容量
for (int num : nums) {
for (int j = p; j >= num; j--) {
dp[j] += dp[j - num];
}
}
return dp[p];
}
}
以 nums=[1,1,1,1,1], target=3（s=5, p=4）为例：
| i\j | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 |
| 2 | 1 | 2 | 1 | 0 | 0 |
| 3 | 1 | 3 | 3 | 1 | 0 |
| 4 | 1 | 4 | 6 | 4 | 1 |
| 5 | 1 | 5 | 10 | 10 | 5 |
最终 dp[5][4]=5（正确答案）。
初始 dp=[1,0,0,0,0]：
dp=[1,1,0,0,0]；dp=[1,2,1,0,0]；dp=[1,3,3,1,0]；dp=[1,4,6,4,1]；dp=[1,5,10,10,5]。这道题是 01 背包的基础布尔型应用（目标是'能否凑满容量'），比'目标和'更贴近 01 背包的原始模型，是理解'01 背包判断可行性'的关键题目。
给定一个只包含正整数的非空数组 nums，判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
nums=[1,5,11,5] → 输出 true（子集 1：[1,5,5]，子集 2：[11]，和均为 11）；nums=[1,2,3,5] → 输出 false（总和 11 为奇数，无法分割）。要分割成两个和相等的子集 → 数组总和 s 必须是偶数（否则直接返回 false）；设目标和 target = s / 2 → 问题转化为：从 nums 中选若干数（每个数只能选 1 次），能否凑出和为 target（01 背包的'可行性判断'）。
target（总和的一半）；dp[i][j] = 考虑前 i 个数字，能否凑出和为 j（true/false）；dp[j] = 能否凑出和为 j（空间优化，压缩 i 维度）。dp[0][0] = true（无数字时，凑出和为 0 的方案存在），dp[0][j>0] = false；dp[0] = true（基准），其余默认 false。核心逻辑：对第 i 个数字（对应 nums[i-1]），分'选'和'不选'两种情况：
if (j >= nums[i-1]) {
// 选：dp[i-1][j-nums[i-1]] OR 不选：dp[i-1][j]
dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i-1]];
} else {
dp[i][j] = dp[i-1][j];
}
for (int num : nums) {
// 倒序遍历：避免同一数字被重复选
for (int j = target; j >= num; j--) {
dp[j] = dp[j] || dp[j - num];
}
}
s 为奇数的情况；num > target 的元素；dp[0]=true。class Solution {
public boolean canPartition(int[] nums) {
int s = 0;
for (int num : nums) s += num;
if (s % 2 != 0) return false;
int target = s / 2;
int n = nums.length;
boolean[][] dp = new boolean[n + 1][target + 1];
dp[0][0] = true;
for (int i = 1; i <= n; i++) {
int num = nums[i - 1];
if (num > target) return false;
for (int j = 0; j <= target; j++) {
if (j >= num) {
dp[i][j] = dp[i-1][j] || dp[i-1][j - num];
} else {
dp[i][j] = dp[i-1][j];
}
}
if (dp[i][target]) return true;
}
return dp[n][target];
}
}
class Solution {
public boolean canPartition(int[] nums) {
int s = 0;
for (int num : nums) s += num;
if (s % 2 != 0) return false;
int target = s / 2;
boolean[] dp = new boolean[target + 1];
dp[0] = true;
for (int num : nums) {
if (num > target) return false;
for (int j = target; j >= num; j--) {
dp[j] = dp[j] || dp[j - num];
}
if (dp[target]) return true;
}
return dp[target];
}
}
以 nums=[1,5,11,5]，s=22，target=11 为例：
| i\j | 0 | 1 | ... | 11 |
|---|---|---|---|---|
| 0 | T | F | ... | F |
| 1（num=1） | T | T | ... | F |
| 2（num=5） | T | T | ... | F |
| 3（num=11） | T | T | ... | T |
遍历到 i=3（num=11）时，dp[3][11]=true，提前返回 true。
初始 dp=[T,F,...,F]：
dp=[T,T,F,...,F]；dp=[T,T,F,...,T,F]；dp=[T,T,F,...,T]（dp[11]=true，提前返回）。| 题目 | 01 背包目标 | 状态转移核心 | 初始化基准 |
|---|---|---|---|
| 分割等和子集 | 可行性（布尔值） | `dp[j] = dp[j] | |
| 目标和 | 方案数（数值） | dp[j] += dp[j-num] | dp[0]=1 |
给定硬币数组 coins（可重复用）和金额 amount，求凑成 amount 的最少硬币数，凑不出返回 -1。示例：coins=[1,2,5], amount=11 → 输出 3（5+5+1）。
物品 = 硬币，容量 = 金额，每个物品可重复选，求「凑满容量的最少物品数」（完全背包求 min）。
dp[i][j] = 考虑前 i 种硬币，凑金额 j 的最少硬币数；dp[j] = 凑金额 j 的最少硬币数。dp[0][0] = 0，dp[0][j>0] = amount+1（标记'不可达'）；dp[0] = 0，其余初始为 amount+1。一维（正序）：
for (int coin : coins) {
for (int j = coin; j <= amount; j++) {
dp[j] = Math.min(dp[j], dp[j - coin] + 1);
}
}
i+1 而非 amount+1；dp[amount] 是否仍为 amount+1。amount+1 是最优（避免溢出）；dp[i] 而非 dp[i-1]。class Solution {
public int coinChange(int[] coins, int amount) {
int n = coins.length;
int[][] dp = new int[n + 1][amount + 1];
for (int j = 1; j <= amount; j++) dp[0][j] = amount + 1;
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
int coin = coins[i-1];
for (int j = 0; j <= amount; j++) {
if (j >= coin) {
dp[i][j] = Math.min(dp[i-1][j], dp[i][j - coin] + 1);
} else {
dp[i][j] = dp[i-1][j];
}
}
}
return dp[n][amount] == amount + 1 ? -1 : dp[n][amount];
}
}
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int coin : coins) {
for (int j = coin; j <= amount; j++) {
dp[j] = Math.min(dp[j], dp[j - coin] + 1);
}
}
return dp[amount] == amount + 1 ? -1 : dp[amount];
}
}
以 coins=[1,2,5], amount=11 为例：
dp=[0,12,12,...,12]；dp=[0,1,2,...,11]；dp=[0,1,1,2,2,3,3,4,4,5,5,6]；dp=[0,1,1,2,2,1,2,2,3,3,2,3]；最终 dp[11]=3。给定整数 n，求组成 n 的最少完全平方数数量。示例：n=12 → 输出 3（4+4+4）。
物品 = 完全平方数（1,4,9,...），容量 = n，物品可重复选，求「凑满容量的最少物品数」。
dp[i][j] = 考虑前 i 个平方数，凑 j 的最少数量；dp[j] = 凑 j 的最少数量。dp[0][0]=0，dp[0][j>0]=j；dp[0]=0，其余初始为 j。一维（正序）：
for (int i = 1; i * i <= n; i++) {
int square = i * i;
for (int j = square; j <= n; j++) {
dp[j] = Math.min(dp[j], dp[j - square] + 1);
}
}
i*i <=n；class Solution {
public int numSquares(int n) {
int maxSquare = (int) Math.sqrt(n);
int[][] dp = new int[maxSquare + 1][n + 1];
for (int j = 1; j <= n; j++) dp[0][j] = j;
dp[0][0] = 0;
for (int i = 1; i <= maxSquare; i++) {
int square = i * i;
for (int j = 0; j <= n; j++) {
if (j >= square) {
dp[i][j] = Math.min(dp[i-1][j], dp[i][j - square] + 1);
} else {
dp[i][j] = dp[i-1][j];
}
}
}
return dp[maxSquare][n];
}
}
class Solution {
public int numSquares(int n) {
int[] dp = new int[n + 1];
for (int j = 1; j <= n; j++) dp[j] = j;
dp[0] = 0;
for (int i = 1; i * i <= n; i++) {
int square = i * i;
for (int j = square; j <= n; j++) {
dp[j] = Math.min(dp[j], dp[j - square] + 1);
}
}
return dp[n];
}
}
以 n=12 为例：
dp=[0,1,2,...,12]；dp[4]=1, dp[8]=2, dp[12]=3；dp[9]=1, dp[12]=min(3, dp[3]+1=4) → 3；最终 dp[12]=3。给定字符串 s 和单词列表 wordDict，判断 s 能否拆分为字典中的单词（单词可重复用）。示例：s="leetcode", wordDict=["leet","code"] → 输出 true。
物品 = 字典单词，容量 = 字符串长度，物品可重复选，求「能否用单词拼接出前 i 个字符」。
dp[i][j] = 考虑前 i 个单词，能否拼接出 s 的前 j 个字符；dp[j] = 能否拼接出 s 的前 j 个字符。dp[0][0] = true；dp[0] = true，其余为 false。一维（正序）：
for (int j = 1; j <= s.length(); j++) {
for (String word : wordDict) {
int len = word.length();
if (j >= len && dp[j - len] && s.substring(j-len, j).equals(word)) {
dp[j] = true;
break;
}
}
}
substring 的左闭右开规则；HashSet 优化字典查询。class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int n = wordDict.size();
int m = s.length();
boolean[][] dp = new boolean[n + 1][m + 1];
dp[0][0] = true;
for (int i = 1; i <= n; i++) {
String word = wordDict.get(i-1);
int len = word.length();
for (int j = 0; j <= m; j++) {
dp[i][j] = dp[i-1][j];
if (j >= len && s.substring(j-len, j).equals(word)) {
dp[i][j] = dp[i][j] || dp[i][j - len];
}
}
}
return dp[n][m];
}
}
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int m = s.length();
boolean[] dp = new boolean[m + 1];
dp[0] = true;
Set<String> wordSet = new HashSet<>(wordDict);
for (int j = 1; j <= m; j++) {
for (String word : wordSet) {
int len = word.length();
if (j >= len && dp[j - len] && s.substring(j-len, j).equals(word)) {
dp[j] = true;
break;
}
}
}
return dp[m];
}
}
以 s="leetcode", wordDict=["leet","code"] 为例：
dp=[true,false,...,false]；substring(0,4)="leet", dp[0]=true → dp[4]=true；substring(4,8)="code", dp[4]=true → dp[8]=true；最终 dp[8]=true。| 维度 | 01 背包 | 完全背包 |
|---|---|---|
| 选取规则 | 物品选 1 次 | 物品可重复选 |
| 遍历顺序 | 先物品→倒序容量 | 先物品→正序容量（可互换） |
| 二维转移 | 依赖 dp[i-1][j-num] | 依赖 dp[i][j-num] |
| 核心应用 | 目标和、分割等和子集 | 最少硬币数、完全平方数 |
| 易错点 | 正序遍历导致重复选 | 贪心陷阱、初始化溢出 |
dp[0]=1；dp[0]=0，其余为极大 / 极小值；dp[0]=true，其余为 false；
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具，Keycode 信息在线工具，online
JavaScript 字符串转义/反转义；Java 风格 \uXXXX（Native2Ascii）编码与解码。 在线工具，Escape 与 Native 编解码在线工具，online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具，JavaScript / HTML 格式化在线工具，online
Terser 压缩、变量名混淆，或 javascript-obfuscator 高强度混淆（体积会增大）。 在线工具，JavaScript 压缩与混淆在线工具，online
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online