参考链接：公众号：代码随想录
题目类型
- 按物品和背包类型：
- 0-1背包
一维数组，去掉物品这个维度，遍历背包时从大到小 - 完全背包
一维数组，去掉物品这个维度，遍历背包时从小到大 - 其他（一般不考）
- 按问题目标：
- 是否问题：
dp[j] = dp[j] || dp[j - nums[i]];
- 最大/最小问题：
dp[j] = Math.max(dp[j], dp[j - nums[i]]+nums[i]);
- 组合/排列问题：
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] 。每件物品都有⽆限个（也就是可以放⼊背包多次），求解将哪些物品装⼊背包⾥物品价值总和最⼤。
遍历顺序：
- 一维数组：遍历顺序先遍历物品，再遍历背包；或者先遍历背包，再遍历物品，都可以。但是遍历背包时，取值从小到大。
- 先遍历物品，再遍历背包
// 先遍历物品，再遍历背包
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]);
}
}
- 先遍历背包，再遍历物品
// 先遍历背包，再遍历物品
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。你可以认为每种硬币的数量是无限的。
遍历顺序先遍历物品，再遍历背包；或者先遍历背包，再遍历物品，都可以。
- 先遍历物品，再遍历背包
// 版本⼀
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];
}
};
- 先遍历背包，再遍历物品
// 版本⼆
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];
}
}
