参考链接：公众号：代码随想录

题目类型

• 按物品和背包类型：

1. 0-1背包
   一维数组，去掉物品这个维度，遍历背包时从大到小
2. 完全背包
   一维数组，去掉物品这个维度，遍历背包时从小到大
3. 其他（一般不考）

• 按问题目标：

1. 是否问题：

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

2. 最大/最小问题：

dp[j] = Math.max(dp[j], dp[j - nums[i]]+nums[i]);

3. 组合/排列问题：

dp[j] += dp[j - nums[i]];

• 组合：先物品后背包
• 排列：先背包后物品

0-1 背包

典型题目

问题	类型
基础0-1背包问题	最大值
494. 目标和	组合数
1049. 最后一块石头的重量 II	最大值
474. 一和零	最大值
416. 分割等和子集	是否问题

基础0-1背包问题

有N件物品和⼀个最多能被重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能⽤⼀次，求解将哪些物品装⼊背包⾥物品价值总和最⼤。

遍历顺序：

• 二维数组：遍历顺序先物品后背包，或者先背包后物品，都可以。遍历背包时，取值从小到大，或从大到小都可以。
• 一维数组：dp数组去掉物品这个维度。遍历顺序先物品后背包，或者先背包后物品，都可以。遍历背包时，取值从大到小。

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包，从大到小
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

完全背包

典型题目

问题	类型
基础完全背包问题	最大值
322. 零钱兑换	最小值
518. 零钱兑换 II	组合数
377. 组合总和 Ⅳ	排列数
279. 完全平方数	最小值
139. 单词拆分	是否问题

基础完全背包问题

有N件物品和⼀个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有⽆限个（也就是可以放⼊背包多次），求解将哪些物品装⼊背包⾥物品价值总和最⼤。

遍历顺序：

• 一维数组：遍历顺序先遍历物品，再遍历背包；或者先遍历背包，再遍历物品，都可以。但是遍历背包时，取值从小到大。

1. 先遍历物品，再遍历背包

// 先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = weight[i]; j < bagWeight ; j++) { // 遍历背包，从小到大
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

2. 先遍历背包，再遍历物品

// 先遍历背包，再遍历物品
for(int j = 0; j <= bagWeight; j++) { // 遍历背包，从小到大
    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        if (j - weight[i] >= 0) {
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }
}

322. 零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。你可以认为每种硬币的数量是无限的。

遍历顺序先遍历物品，再遍历背包；或者先遍历背包，再遍历物品，都可以。

1. 先遍历物品，再遍历背包

// 版本⼀
class Solution {
    public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 0; i < coins.size(); i++) { // 遍历物品
            for (int j = coins[i]; j <= amount; j++) { // 遍历背包，从小到大
                if (dp[j - coins[i]] != INT_MAX) { // 如果dp[j - coins[i]]是初始
                    值则跳过
                    dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
                }
            }
        }
        if (dp[amount] == INT_MAX) return -1;
        return dp[amount];
    }
};

2. 先遍历背包，再遍历物品

// 版本⼆
class Solution {
    public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) { // 遍历背包，从小到大
            for (int j = 0; j < coins.size(); j++) { // 遍历物品
                if (i - coins[j] >= 0 && dp[i - coins[j]] != INT_MAX ) {
                    dp[i] = min(dp[i - coins[j]] + 1, dp[i]);
                }
            }
        }
        if (dp[amount] == INT_MAX) return -1;
        return dp[amount];
    }
};

518. 零钱兑换 II

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。
假设每一种面额的硬币有无限个。

求组合数，所以遍历顺序：先遍历物品，再遍历背包。

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < coins.size(); i++) { // 遍历物品
            for (int j = coins[i]; j <= amount; j++) { // 遍历背包，从小到大
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];
    }
};

377. 组合总和 Ⅳ

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。题目数据保证答案符合 32 位整数范围。

示例 1：
输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。
nums 中的所有元素 互不相同。
数组中的元素可以被多次使用。

题目名字是“组合”，但其实求的是排列。所以遍历顺序：先遍历背包，再遍历物品。

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target+1];
        dp[0]=1;
        for(int t=1;t<=target;t++){ // 遍历背包，从小到大
            for(int i=0;i<nums.length;i++){ // 遍历物品
                if(t-nums[i]>=0){
                    dp[t] += dp[t-nums[i]];
                }
            }
        }
        return dp[target];
    }
}

279. 完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。

遍历顺序先遍历物品，再遍历背包；或者先遍历背包，再遍历物品，都可以。

139. 单词拆分

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

遍历顺序先遍历物品，再遍历背包；或者先遍历背包，再遍历物品，都可以。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> set = new HashSet<>(wordDict);
        int len = s.length();
        // dp[i] : dp[i]为true，表示 s[0,i-1]可以拆分为⼀个或多个在字典中出现的单词
        boolean[] dp = new boolean[len+1];
        dp[0]=true;
        for(int i=1;i<len+1;i++){ // 遍历背包
            for(int j=0;j<i;j++){ // 遍历物品
                if(dp[j] && set.contains(s.substring(j,i))){
                    dp[i]=true;
                    break;
                }
            }
        }
        return dp[len];
    }
}