代码随想录算法训练营Day37 | 完全背包基础理论 518. 零钱兑换II 377. 组合总和Ⅳ 57. 爬楼梯（第八期模拟笔试）

完全背包基础理论

• 不放物品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的价值），就是背包放物品i得到的最大价值

递推公式： dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);

（注意，完全背包二维dp数组 和 01背包二维dp数组 递推公式的区别，01背包中是 dp[i - 1][j - weight[i]] + value[i])）

状态转移方程​​

背包类型	状态转移方程（二维DP）	状态转移方程（一维DP）
​​0-1背包​​	dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)	dp[j] = max(dp[j], dp[j-w] + v)（​​逆序​​更新）
​​完全背包​​	dp[i][j] = max(dp[i-1][j], dp[i][j-w] + v)	dp[j] = max(dp[j], dp[j-w] + v)（​​正序​​更新）

518. 零钱兑换II

问题描述：

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。 

题目数据保证结果符合 32 位带符号整数。

解决方式：

class Solution {public int change(int amount, int[] coins) {int count = coins.length;//dp[i][j]表示前i个硬币凑够容量为j的包有多少种方法int[][] dp = new int[count][amount + 1];//初始化背包大小为0的情况for (int i = 0; i < coins.length; i++) {// 第一列的初始值为1dp[i][0] = 1;}//初始化只有第一种硬币的情况for (int j = 0; j <= amount; j++) {if (j % coins[0] == 0)dp[0][j] = 1;}for (int i = 1; i < count; i++) {for (int j = 1; j <= amount; j++) {if (j < coins[i]) {dp[i][j] = dp[i - 1][j];} else {//不选当前硬币的方法数 + 选当前硬币的方法数dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]];}}}return dp[count-1][amount];}
}

377. 组合总和Ⅳ

问题描述：

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

解决方式：

和爬楼梯一种做法，注意这里的排列需要要先遍历target再遍历nums

class Solution {public int combinationSum4(int[] nums, int target) {int[] dp = new int[target + 1];dp[0] = 1; // 总和为 0 时，只有一种方法（不选任何数）for (int i = 0; i <= target; i++) { // 遍历所有可能的总和 ifor (int j = 0; j < nums.length; j++) { // 遍历所有 nums[j]if (i >= nums[j]) { // 如果 nums[j] 可以选dp[i] += dp[i - nums[j]]; // 累加 dp[i - nums[j]]}}}return dp[target]; // 返回总和为 target 的排列数}
}

57. 爬楼梯（第八期模拟笔试）

问题描述：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 

每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？ 

注意：给定 n 是一个正整数。

解决方式：

import java.util.*;
public class Main{public static int combinationSum4(int[] nums, int target) {int[] dp = new int[target + 1];dp[0] = 1; // 总和为 0 时，只有一种方法（不选任何数）for (int i = 1; i <= target; i++) { // 遍历所有可能的总和 ifor (int n : nums) { // 遍历所有 numsif (i >= n) {dp[i] += dp[i - n];}}}return dp[target]; // 返回总和为 target 的排列数}public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int[] nums = new int[m];for(int i=0;i<m;i++){nums[i] = i+1;}int res =  combinationSum4(nums,n);System.out.println(res);}
}