动态规划：01 背包与完全背包题型总结

初始化

• 二维：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]; // 选 + 不选的叠加
      }
  }
  

4. 易错点

1. 变量名混淆：用 target 存总和，导致逻辑混乱（需单独用 s 存总和，p 存目标和）；
2. 遍历顺序错误：正序遍历容量→变成完全背包（重复选数）；
3. 合法性判断缺失：未判断 (target+s) 是否为偶数、p 是否非负；
4. 初始化遗漏：未设 dp[0]=1（基准丢失，结果全 0）。

5. 难点

1. 问题转化：从「加减符号」抽象出「01 背包」的思维跳跃；
2. 一维遍历逻辑：倒序的底层原因（避免重复选数）；
3. 边界处理：p 为负 / 总和小于 |target| 的特殊情况。

6. Java 实现

二维 DP 解法

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];
    }
}

一维 DP 解法（空间优化）

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];
    }
}

7. 过程展示

以 nums=[1,1,1,1,1], target=3（s=5, p=4）为例：

二维 DP 表填充（关键行）

最终 dp[5][4]=5（正确答案）。

一维 DP 更新过程

初始 dp=[1,0,0,0,0]：

• 遍历第 1 个 1：dp=[1,1,0,0,0]；
• 遍历第 2 个 1：dp=[1,2,1,0,0]；
• 遍历第 3 个 1：dp=[1,3,3,1,0]；
• 遍历第 4 个 1：dp=[1,4,6,4,1]；
• 遍历第 5 个 1：dp=[1,5,10,10,5]。

（二）分割等和子集（416）

这道题是 01 背包的基础布尔型应用（目标是'能否凑满容量'），比'目标和'更贴近 01 背包的原始模型，是理解'01 背包判断可行性'的关键题目。

1. 题目描述

给定一个只包含正整数的非空数组 nums，判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

• 示例 1：输入 nums=[1,5,11,5] → 输出 true（子集 1：[1,5,5]，子集 2：[11]，和均为 11）；
• 示例 2：输入 nums=[1,2,3,5] → 输出 false（总和 11 为奇数，无法分割）。

2. 问题转化（01 背包核心）

2.1 核心推导

要分割成两个和相等的子集 → 数组总和 s 必须是偶数（否则直接返回 false）；设目标和 target = s / 2 → 问题转化为：从 nums 中选若干数（每个数只能选 1 次），能否凑出和为 target（01 背包的'可行性判断'）。

2.2 对应背包模型

• 物品：数组中的每个数字（每个只能选 1 次）；
• 容量：target（总和的一半）；
• 目标：判断'能否用物品装满容量'（布尔值）。

3. 详细分析

3.1 状态定义

• 二维 DP：dp[i][j] = 考虑前 i 个数字，能否凑出和为 j（true/false）；
• 一维 DP：dp[j] = 能否凑出和为 j（空间优化，压缩 i 维度）。

3.2 初始化（基准状态）

• 二维：dp[0][0] = true（无数字时，凑出和为 0 的方案存在），dp[0][j>0] = false；
• 一维：dp[0] = true（基准），其余默认 false。

3.3 状态转移

核心逻辑：对第 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];
}

一维转移（倒序！01 背包核心）

for (int num : nums) {
    // 倒序遍历：避免同一数字被重复选
    for (int j = target; j >= num; j--) {
        dp[j] = dp[j] || dp[j - num];
    }
}

4. 易错点

1. 总和奇偶性判断缺失：直接开始 DP，忽略 s 为奇数的情况；
2. 遍历顺序错误：正序遍历容量→变成完全背包；
3. 元素剪枝遗漏：数组中存在 num > target 的元素；
4. 初始化错误：未设 dp[0]=true。

5. 难点

1. 问题抽象能力：从'分割子集'到'01 背包可行性'的转化；
2. 提前剪枝优化：总和为奇数、单个元素过大、DP 过程中提前找到可行方案；
3. 一维遍历的逻辑理解：倒序的本质是'保证每个数字只选一次'。

6. Java 实现

1. 二维 DP 解法

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];
    }
}

2. 一维 DP 解法

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];
    }
}

7. 过程展示

以 nums=[1,5,11,5]，s=22，target=11 为例：

7.1 二维 DP 表填充（关键行）

遍历到 i=3（num=11）时，dp[3][11]=true，提前返回 true。

7.2 一维 DP 更新过程

初始 dp=[T,F,...,F]：

• 遍历 num=1：dp=[T,T,F,...,F]；
• 遍历 num=5：dp=[T,T,F,...,T,F]；
• 遍历 num=11：dp=[T,T,F,...,T]（dp[11]=true，提前返回）。

8. 与'目标和'的对比

三、完全背包典型题目

（一）最少硬币数（322）

1. 题目描述

给定硬币数组 coins（可重复用）和金额 amount，求凑成 amount 的最少硬币数，凑不出返回 -1。示例：coins=[1,2,5], amount=11 → 输出 3（5+5+1）。

2. 问题转化

物品 = 硬币，容量 = 金额，每个物品可重复选，求「凑满容量的最少物品数」（完全背包求 min）。

3. 详细分析

状态定义

• 二维：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);
    }
}

4. 易错点

1. 初始化错误：用 i+1 而非 amount+1；
2. 结果判断缺失：未检查 dp[amount] 是否仍为 amount+1。

5. 难点

1. 不可达标记选择：amount+1 是最优（避免溢出）；
2. 完全背包的'重复选'逻辑：二维用 dp[i] 而非 dp[i-1]。

6. Java 实现

二维 DP 解法

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];
    }
}

一维 DP 解法

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];
    }
}

7. 过程展示

以 coins=[1,2,5], amount=11 为例：

• 一维初始 dp=[0,12,12,...,12]；
• 遍历 coin=1：dp=[0,1,2,...,11]；
• 遍历 coin=2：dp=[0,1,1,2,2,3,3,4,4,5,5,6]；
• 遍历 coin=5：dp=[0,1,1,2,2,1,2,2,3,3,2,3]；最终 dp[11]=3。

（二）完全平方数的最少数量（279）

1. 题目描述

给定整数 n，求组成 n 的最少完全平方数数量。示例：n=12 → 输出 3（4+4+4）。

2. 问题转化

物品 = 完全平方数（1,4,9,...），容量 = n，物品可重复选，求「凑满容量的最少物品数」。

3. 详细分析

状态定义

• 二维：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);
    }
}

4. 易错点

1. 贪心陷阱：优先选最大平方数；
2. 平方数遍历边界：未限制 i*i <=n；
3. 状态转移遗漏：未取 min。

5. 难点

1. 贪心 vs DP 的取舍；
2. 数学定理优化：拉格朗日四平方和定理。

6. Java 实现

二维 DP 解法

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];
    }
}

一维 DP 解法

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];
    }
}

7. 过程展示

以 n=12 为例：

• 一维初始 dp=[0,1,2,...,12]；
• 遍历 square=1：无变化；
• 遍历 square=4：dp[4]=1, dp[8]=2, dp[12]=3；
• 遍历 square=9：dp[9]=1, dp[12]=min(3, dp[3]+1=4) → 3；最终 dp[12]=3。

（三）单词拆分（139）

1. 题目描述

给定字符串 s 和单词列表 wordDict，判断 s 能否拆分为字典中的单词（单词可重复用）。示例：s="leetcode", wordDict=["leet","code"] → 输出 true。

2. 问题转化

物品 = 字典单词，容量 = 字符串长度，物品可重复选，求「能否用单词拼接出前 i 个字符」。

3. 详细分析

状态定义

• 二维：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;
        }
    }
}

4. 易错点

1. 贪心陷阱：用 flag 锁定拆分位置；
2. 索引错误：substring 的左闭右开规则；
3. 查询效率低：未用 HashSet 优化字典查询。

5. 难点

1. 字符串与背包的转化；
2. 子串截取的边界处理；
3. 布尔值的状态转移。

6. Java 实现

二维 DP 解法

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];
    }
}

一维 DP 解法（优化）

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];
    }
}

7. 过程展示

以 s="leetcode", wordDict=["leet","code"] 为例：

• 一维初始 dp=[true,false,...,false]；
• j=4：substring(0,4)="leet", dp[0]=true → dp[4]=true；
• j=8：substring(4,8)="code", dp[4]=true → dp[8]=true；最终 dp[8]=true。

四、整体总结

1. 01 背包 vs 完全背包核心对比

2. 解题通用步骤

1. 识别背包类型：判断物品能否重复选（01 / 完全）；
2. 抽象物品 & 容量：
   • 01 背包：物品 = 数字，容量 = 目标和；
   • 完全背包：物品 = 硬币 / 平方数 / 单词，容量 = 金额 / 数值 / 字符串长度；
3. 定义状态：二维（易理解）→ 一维（空间优化）；
4. 初始化基准：
   • 方案数：dp[0]=1；
   • 最值：dp[0]=0，其余为极大 / 极小值；
   • 布尔值：dp[0]=true，其余为 false；
5. 状态转移：基于「选 / 不选」推导，取 min/max/ 叠加 / 或；
6. 遍历顺序：按背包类型确定，验证边界。

3. 关键思维

• DP 的核心是「覆盖所有路径」，而非贪心的「局部最优」；
• 二维 DP 是理解本质的基础，一维 DP 是刷题的最优选择；
• 背包问题的本质是「状态的复用」，遍历顺序决定复用规则。