代码随想录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) {
                // 若超过背包容量，则不选物品 i
                dp[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) {
                // 若超过背包容量，则不选物品 i
                dp[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]);
        }
    }
}