第九章 动态规划 part05
力扣上没有纯粹的完全背包的题目，我在卡码网上制作了题目，大家可以去做一做，题目链接在下面的文章链接里。
后面的两道题目，都是完全背包的应用，做做感受一下
完全背包
视频讲解：https://www.bilibili.com/video/BV1uK411o7c9
第一个问题 ：
为什么可以正序
不完全依赖过去行的状态 而是更依赖之前的状态
为什么可以颠倒
正序向前 依赖前一个状态 所以可以更新
518. 零钱兑换 II
视频讲解：https://www.bilibili.com/video/BV1KM411k75j
https://programmercarl.com/0518.%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2II.html
错误：
class Solution {
public int change(int amount, int[] coins) {
int n = coins.length;
int[] dp = new int[n+1];// 想想dp数组含义
dp[0] = 1;
for(int i = 0; i < coins.length; i ++){
for(int j = coins[i]; j <= amount; j ++){
dp[j] = dp[j] + dp[j - coins[i]];
}
}
return dp[amount];
}
}
正确：
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] + dp[j - coins[i]];
}
}
return dp[amount];
}
}
377. 组合总和 Ⅳ
视频讲解：https://www.bilibili.com/video/BV1V14y1n7B6
https://programmercarl.com/0377.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C%E2%85%A3.html
class Solution {
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for(int j = 0; j <= target; j ++){
for(int i = 0; i < nums.length && j >= nums[i]; i ++){
dp[j] = dp[j] + dp[j - nums[i]];
}
}
return dp[target];
}
}
nums =
[3,1,2,4]
target =
4
输出
2
预期结果
8
排序：
class Solution {
public int combinationSum4(int[] nums, int target) {
Arrays.sort(nums);
int[] dp = new int[target + 1];
dp[0] = 1;
for(int j = 0; j <= target; j ++){
for(int i = 0; i < nums.length && j >= nums[i]; i ++){
dp[j] = dp[j] + dp[j - nums[i]];
}
}
return dp[target];
}
}
或者：
classSolution{publicintcombinationSum4(int[]nums,inttarget){int[]dp=newint[target+1];dp[0]=1;for(inti=0;i<=target;i++){for(intj=0;j<nums.length;j++){if(i>=nums[j]){dp[i]+=dp[i-nums[j]];}}}returndp[target];}}
70. 爬楼梯 （进阶）
这道题目 爬楼梯之前我们做过，这次再用完全背包的思路来分析一遍
importjava.util.Scanner;classclimbStairs{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);intm,n;while(sc.hasNextInt()){// 从键盘输入参数，中间用空格隔开n=sc.nextInt();m=sc.nextInt();// 求排列问题，先遍历背包再遍历物品int[]dp=newint[n+1];dp[0]=1;for(intj=1;j<=n;j++){for(inti=1;i<=m;i++){if(j-i>=0)dp[j]+=dp[j-i];}}System.out.println(dp[n]);}}}
