代码随想录day32：动态规划part5
完全背包
二维
/* 完全背包：动态规划 */
int unboundedKnapsackDP(int[] wgt, int[] val, int cap) {int n = wgt.length;// 初始化 dp 表int[][] dp = new int[n + 1][cap + 1];// 状态转移for (int i = 1; i <= n; i++) {for (int c = 1; c <= cap; c++) {if (wgt[i - 1] > c) {// 若超过背包容量，则不选物品 idp[i][c] = dp[i - 1][c];} else {// 不选和选物品 i 这两种方案的较大值dp[i][c] = Math.max(dp[i - 1][c], dp[i][c - wgt[i - 1]] + val[i - 1]);}}}return dp[n][cap];
}
一维
/* 完全背包：空间优化后的动态规划 */
int unboundedKnapsackDPComp(int[] wgt, int[] val, int cap) {int n = wgt.length;// 初始化 dp 表int[] dp = new int[cap + 1];// 状态转移for (int i = 1; i <= n; i++) {for (int c = 1; c <= cap; c++) {if (wgt[i - 1] > c) {// 若超过背包容量，则不选物品 idp[c] = dp[c];} else {// 不选和选物品 i 这两种方案的较大值dp[c] = Math.max(dp[c], dp[c - wgt[i - 1]] + val[i - 1]);}}}return dp[cap];
}由于当前状态是从左边和上边的状态转移而来的，因此空间优化后应该对 dp 表中的每一行进行正序遍历。
这个遍历顺序与 0-1 背包正好相反。hello算法讲解的很清楚。
518. 零钱兑换 II
class Solution {public int change(int amount, int[] coins) {int[] dp = new int[amount + 1];dp[0] = 1;for(int i = 1; i <= coins.length; i++){for(int j = 0; j <= amount; j++){if(coins[i - 1] > j){dp[j] = dp[j];}else{dp[j] = dp[j] + dp[j - coins[i - 1]];}}}return dp[amount];}
}零钱换整1
就是完全背包min问题，初始化最上边一行为max = amount + 1用与比较
零钱换整2
就是方案问题，
二维方案问题
for (int i = 0; i <= n; i++) {dp[i][0] = 1;}“在前0个数字中，凑出和为0的组合，有几种方法”，我们只能选择放弃“第0个数字”
一维就dp[0] = 1;就行，其实一维的好写，不用考虑遍历边界。
状态转移跟494. 目标和第一个做的方案问题一样，改成完全背包的形式，正序遍历。
377. 组合总和 Ⅳ
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 = 1; i <= nums.length; i++){if(j - nums[i - 1] >= 0){dp[j] = dp[j] + dp[j - nums[i - 1]];}}}return dp[target];}
}跟上一题的区别就是上一题是组合问题，这次是排列问题。
第一种遍历顺序（组合数）
for (int i = 0; i < coins.size(); i++) { // 遍历物品for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量dp[j] += dp[j - coins[i]];}
}
- 分析:
- 外层循环遍历每种硬币。在计算时，内层循环从当前硬币的面额开始，更新所有可能的金额。
- 这种方式确保了对于每种硬币，只能在其面额之后进行更新，导致
dp数组中只计算组合，避免重复计数。
第二种遍历顺序（排列数）
for (int j = 0; j <= amount; j++) { // 遍历背包容量for (int i = 0; i < coins.size(); i++) { // 遍历物品if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];}
}
- 分析:
- 外层循环遍历每个可能的金额，内层循环遍历每种硬币。
- 在这种顺序下，每个金额
j都会考虑每种硬币的组合，导致dp[j]中包含了所有可能的排列。
-
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
70. 爬楼梯（进阶版）
改为：一步一个台阶，两个台阶，三个台阶，.......，直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢？
这又有难度了，这其实是一个完全背包问题。
1阶，2阶，.... m阶就是物品，楼顶就是背包。
每一阶可以重复使用，例如跳了1阶，还可以继续跳1阶。
问跳到楼顶有几种方法其实就是问装满背包有几种方法。
import java.util.Scanner;
class climbStairs{public static void main(String [] args){Scanner sc = new Scanner(System.in);int m, n;while (sc.hasNextInt()) {// 从键盘输入参数，中间用空格隔开n = sc.nextInt();m = sc.nextInt();// 求排列问题，先遍历背包再遍历物品int[] dp = new int[n + 1];dp[0] = 1;for (int j = 1; j <= n; j++) {for (int i = 1; i <= m; i++) {if (j - i >= 0) dp[j] += dp[j - i];}}System.out.println(dp[n]);}}
}