完全背包
题目链接：完全背包
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰完全背包
日期：2024-10-11
想法：dp数组设置思路跟01背包一样，不同在遍历上，完全背包遍历背包大小是从weight[i]开始的（背包空间小于weight[i]就没有意义，不用考虑，直接用之前的对应数值就行了），从前往后遍历就能够是重复使用物品i的效果。
Java代码如下：
import java.util.Scanner;public class Main {public static void main (String[] args) {Scanner scanner = new Scanner(System.in);int N = scanner.nextInt();int bagweight = scanner.nextInt();int[] weight = new int[N];int[] value = new int[N];for(int i = 0; i < N; i++) {int w = scanner.nextInt();int v = scanner.nextInt();weight[i] = w;value[i] = v;}int[] dp = new int[bagweight + 1];for(int i = 0; i < N; i++) {for(int j = weight[i]; j <= bagweight; j++) {dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);}}System.out.println(dp[bagweight]);}
}
518. 零钱兑换 II
题目链接：518. 零钱兑换 II
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰零钱兑换 II
日期：2024-10-11
想法：求组合数的问题+完全背包，唯一难点在于初始化dp[0]，按理说dp[0]代表：有多少组合能让零钱和为0，按理应该是0，但这里要设置为1，才能保证j = amount时有个加1的效果。
Java代码如下：
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];}
}
377. 组合总和 Ⅳ
题目链接：377. 组合总和 Ⅳ
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰组合总和 Ⅳ
日期：2024-10-11
想法：组合{1，3}{3，1}为不同组合，如果再按照上一题的思路，只能计算一次{1，3}，找不完所有组合，但遍历顺序反一下，从背包大小为0开始，在遍历nums，就会有{1，3}{3，1}这两种情况了，同时注意，此时i为背包大小，要i >= nums[j]时才放的下nums中第j个数。
Java代码如下：
class Solution {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];}
}
70. 爬楼梯 （进阶）
题目链接：70. 爬楼梯 （进阶）
文档讲解︰代码随想录(programmercarl.com)
日期：2024-10-11
想法：完全背包的思路解决。
Java代码如下：
import java.util.Scanner;public class Main {public static void main (String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int[] dp = new int[n + 1];dp[0] = 1;for(int i = 0; i <= n; i++) {for(int j = 1; j <= m; j++) {if(i >= j) {dp[i] += dp[i - j]; }}}System.out.println(dp[n]);}
}
