Day 42 || 完全背包、518. 零钱兑换 II 、 377. 组合总和 Ⅳ、70. 爬楼梯（进阶）

2024/11/7 15:34:02 来源：https://blog.csdn.net/qq_43408590/article/details/143473687 浏览: 次关键词：Day 42 || 完全背包、518. 零钱兑换 II 、 377. 组合总和 Ⅳ、70. 爬楼梯（进阶）

完全背包

题目链接：卡码网第52题

思路：和之前01背包一样，但是物品可以无限放置，所以之前二维数组中的背包容量是倒序遍历的，现在可以正序遍历即可重复放入。

import java.util.Scanner;
public class Main {public static void main (String[] args) {Scanner scaner = new Scanner(System.in);int kind = scaner.nextInt();int size = scaner.nextInt();int[] weight = new int[kind];int[] value = new int[kind];for (int i=0;i<kind;i++){weight[i]=scaner.nextInt();value[i]=scaner.nextInt();}int[][] dp = new int[kind+1][size+1];for(int i=1;i<=kind;i++){for (int j=0;j<=size;j++){if(j>=weight[i-1]){dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weight[i - 1]] + value[i - 1]);}else {dp[i][j] = dp[i - 1][j]; // 如果不能放入第 i 件物品}        }}System.out.println(dp[kind][size]);}
}

518. 零钱兑换 II

题目链接：力扣题目链接

思路：因为是可以无限使用相同规格的金币，完全背包和之前一样容量正序即可；但是需要注意的是因为是求可能性的数量所以需要初始化容量为0时候为1。

//一维
class Solution {public int change(int amount, int[] coins) {int[] dp = new int[amount + 1];dp[0] = 1; // 初始状态，凑成金额0的组合数为1（即什么都不选）for (int coin : coins) {for (int i = coin; i <= amount; i++) {dp[i] += dp[i - coin];}}return dp[amount];}
}//二维
class Solution {public int change(int amount, int[] coins) {int[][] dp = new int[coins.length + 1][amount + 1];// 初始化：凑成金额0的方法只有1种，即不选任何硬币for (int j = 0; j <= coins.length; j++) {dp[j][0] = 1;}// 填充 dp 表for (int j = 1; j <= coins.length; j++) {for (int i = 0; i <= amount; i++) {if (i >= coins[j - 1]) {// 使用当前硬币或不使用当前硬币的组合数dp[j][i] = dp[j - 1][i] + dp[j][i - coins[j - 1]];} else {// 无法使用当前硬币，只能继承上一个状态的组合数dp[j][i] = dp[j - 1][i];}}}return dp[coins.length][amount];}
}