代码随想录算法训练营第三十七天 | 完全背包理论基础、518-零钱兑换Ⅱ、377-组合总和Ⅳ
完全背包理论基础
文章讲解：https://programmercarl.com/背包问题理论基础完全背包.html
视频讲解：https://www.bilibili.com/video/BV1uK411o7c9/
完全背包和01背包问题唯一不同的就是，在完全背包问题中每种物品有无限件
先来推导完全背包问题的二维dp数组形式，动规五部曲：
- 确定dp数组以及下标的含义
dp[i][j]表示从下标为[0, i]的物品，每个物品可取无限次，放进容量为j的背包，价值总和最大为dp[i][j]
- 确定递推公式
状态转移方程 dp[i][j] = Math.max(dp[i-1][j]，dp[i][j-weight[i]] + value[i])
不放物品i：背包容量为 j，里面不放物品 i 的最大价值为dp[i-1][j]
放物品i：背包空出一个物品i的容量后，背包容量为 j-weight[i]，即 dp[i][j-weight[i]] 为背包容量为 j-weight[i]且不放物品 i 的最大价值，所以 dp[i][j-weight[i]] + value[i] 就是背包放物品 i 得到的最大价值
- dp数组如何初始化
当 j=0，即背包容量为0时，放不下任何物品，所以价值一定为0，故第零列初始化为0
当 i=0时，dp[0][j]表示放物品0时，各个容量的背包所能存放的最大价值
- 确定遍历顺序
根据递推公式，dp的值是由上方和左方dp推导而来
外层for顺序遍历物品i，内层for顺序遍历容量j
- 举例推导dp数组
接着继续推导完全背包问题的一维dp数组形式，动规五部曲：
- 确定dp数组以及下标的含义
dp[j]表示在每个可取无限次的物品中，选取若干个放进容量为j的背包，价值总和最大为dp[j]
- 确定递推公式
状态转移方程 dp[j] = Math.max(dp[j]，dp[j-weight[i]] + value[i])
- dp数组如何初始化
全初始化为0
- 确定遍历顺序
外层for顺序遍历物品i，内层for顺序遍历容量j
- 举例推导dp数组
LeetCode518 零钱兑换Ⅱ
题目链接：https://leetcode.cn/problems/coin-change-ii/description/
文章讲解：https://programmercarl.com/0518.零钱兑换II.html
视频讲解：https://www.bilibili.com/video/BV1KM411k75j/
动规五部曲：
- 确定dp数组以及下标的含义
dp[j]表示装满容量为j的背包有dp[j]种方法
- 确定递推公式
不放物品i：即背包容量为j，里面不放物品i，装满有dp[i-1][j]种方法
放物品i：即先空出物品i的容量，背包容量为j-coins[i]，装满有dp[i][j-coins[i]]种方法
if(j - coins[i] >= 0){dp[i][j] = dp[i-1][j] + dp[i][j-coins[i]];
}else{dp[i][j] = dp[i-1][j];
}
转化为一维dp，状态转移方程 dp[j] += dp[j-coins[i]]
- dp数组如何初始化
dp[0] = 1，即不放任何物品算作一种方法；其他非零下标初始化为0
- 确定遍历顺序
先遍历物品，后遍历背包，得到的是组合数
先遍历背包，后遍历物品，得到的是排列数
本题要求的是组合数，所以是外层for顺序遍历物品，内层for顺序遍历背包
- 举例推导dp数组
class Solution {public int change(int amount, int[] coins) {int[] dp = new int[amount + 1];dp[0] = 1;for(int i = 0; i < coins.length; i++){for(int j = coins[i]; j <= amount; j++){dp[j] += dp[j-coins[i]];}}return dp[amount];}
}
LeetCode377 组合总和Ⅳ
题目链接：https://leetcode.cn/problems/combination-sum-iv/description/
文章讲解：https://programmercarl.com/0377.组合总和Ⅳ.html
视频讲解：https://www.bilibili.com/video/BV1V14y1n7B6/?vd_source=b989f2b109eb3b17e8178154a7de7a51
动规五部曲：
- 确定dp数组以及下标的含义
dp[j]表示装满容量为j的背包有dp[j]种方法
- 确定递推公式
不放物品i：即背包容量为j，里面不放物品i，装满有dp[i-1][j]种方法
放物品i：即先空出物品i的容量，背包容量为j-nums[i]，装满有dp[i][j-nums[i]]种方法
if(j - nums[i] >= 0){dp[i][j] = dp[i-1][j] + dp[i][j-nums[i]];
}else{dp[i][j] = dp[i-1][j];
}
转化为一维dp，状态转移方程 dp[j] += dp[j-nums[i]]
- dp数组如何初始化
dp[0] = 1，即不放任何物品算作一种方法；其他非零下标初始化为0
- 确定遍历顺序
先遍历物品，后遍历背包，得到的是组合数
先遍历背包，后遍历物品，得到的是排列数
本题要求的是排列数，所以是外层for顺序遍历背包，内层for顺序遍历物品
- 举例推导dp数组
class Solution {public int combinationSum4(int[] nums, int target) {int[] dp = new int[target+1];dp[0] = 1;for(int j = 1; j <= target; j++){for(int i = 0; i < nums.length; i++){if(j - nums[i] >= 0){dp[j] += dp[j-nums[i]];}}}return dp[target];}
}