背包问题终极速查表原创

# 背包问题终极速查表


dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];
dp[i][j]装满背包为j,使用[0,i]的物品的方法数 等于如下：
dp[i-1][j] 即不使用当前的物品i 的所有方法数加上下面的方法数
dp[i-1][j-nums[i]]

if(j<nums[i]){
	dp[i][j]=dp[i-1][j];
}else{
	dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]];
}

1
2
3
4
5
6
7
8
9
10
11
12

# 背包问题终极速查表（直接背，刷题无敌）

# 一、两大核心顺序

先遍历物品，再遍历背包
含义：不计顺序 → 求组合数
适用：元素不分先后，1+2 和 2+1 算一种
先遍历背包，再遍历物品
含义：计较顺序 → 求排列数
适用：顺序不同算不同方案

# 二、内外层 + 正倒序万能判定

# 1. 01 背包（物品只能选 1 次）

遍历顺序：先物品 → 后背包
背包遍历：从大到小倒序
用途：最大价值、最多物品、分割等和子集、一和零

for(物品)
    for(容量=max; 容量>=w; 容量--)

1
2

# 2. 完全背包（物品无限选）

# ① 求组合数（不计顺序）

顺序：先物品 → 后背包
背包：从小到大正序
例题：零钱兑换 II、凑和组合数

java

运行

for(物品)
    for(容量=w; 容量<=max; 容量++)

1
2

# ② 求排列数（计较顺序）

顺序：先背包 → 后物品
背包：从小到大正序
例题：组合总和 Ⅳ（combinationSum4）

for(容量)
    for(物品)

1
2

public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 0; i <= target; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (i >= nums[j]) {
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }

1
2
3
4
5
6
7
8
9
10
11
12

# 三、状态转移公式区分

求最大数量 / 最大价值
适用：一和零、基础 01 背包


dp[j] = Math.max(dp[j], dp[j-w]+val);

1
2
3

求方案总数（凑法数量）
适用：目标和、零钱兑换、组合总和


dp[j] += dp[j - w];

1
2
3

求最少个数
适用：零钱兑换 Ⅰ 最少硬币


dp[j] = Math.min(dp[j], dp[j-w]+1);

1
2
3

# 四、高频真题一秒区分

表格

题目	类型	遍历顺序	背包顺序
分割等和子集	01 背包判断	先物品后背包	倒序
目标和	01 背包计数	先物品后背包	倒序
一和零	二维 01 背包	先物品后背包	倒序
零钱兑换 II	完全背包组合	先物品后背包	正序
组合总和 Ⅳ	完全背包排列	先背包后物品	正序
爬楼梯	完全背包排列	先背包后物品	正序

# 五、最简口诀

01 倒序，完全正序

组合先物后排包，排列先包后排物

最值用 max，计数用累加，最少用 min

# 六、初始化小规则

求方案数：dp[0] = 1，其余 0
求最大价值：全初始 0
求最少数目：初始最大值，dp[0]=0

编辑

#思源