代码随想录算法训练营第37天

**完全背包 **

视频讲解：带你学透完全背包问题！ 和 01背包有什么差别？遍历顺序上有什么讲究？_哔哩哔哩_bilibili

https://programmercarl.com/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%98%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85.html

private static void testCompletePack() {
    int[] itemWeights = {1, 3, 4};
    int[] itemValues = {15, 20, 30};
    int maxBagWeight = 4;
    int[] packValues = new int[maxBagWeight + 1];
    for (int i = 0; i < itemWeights.length; i++) {
        for (int j = itemWeights[i]; j <= maxBagWeight; j++) {
            packValues[j] = Math.max(packValues[j], packValues[j - itemWeights[i]] + itemValues[i]);
        }
    }
    for (int currentMax : packValues) {
        System.out.println(currentMax + "   ");
    }
}

**518. 零钱兑换 II **

视频讲解：动态规划之完全背包，装满背包有多少种方法？组合与排列有讲究！| LeetCode：518.零钱兑换II_哔哩哔哩_bilibili

代码随想录

class Solution {
    public int change(int totalAmount, int[] coinValues) {
        int[] combinations = new int[totalAmount + 1];
        combinations[0] = 1;
        for (int i = 0; i < coinValues.length; i++) {
            for (int j = coinValues[i]; j <= totalAmount; j++) {
                combinations[j] += combinations[j - coinValues[i]];
            }
        }
        return combinations[totalAmount];
    }
}

**377. 组合总和 Ⅳ **

视频讲解：动态规划之完全背包，装满背包有几种方法？求排列数？| LeetCode：377.组合总和IV_哔哩哔哩_bilibili

代码随想录

class Solution {
    public int combinationSum4(int[] candidates, int sum) {
        int[] combinationsCount = new int[sum + 1];
        combinationsCount[0] = 1;
        for (int currentSum = 0; currentSum <= sum; currentSum++) {
            for (int candidate : candidates) {
                if (currentSum >= candidate) {
                    combinationsCount[currentSum] += combinationsCount[currentSum - candidate];
                }
            }
        }
        return combinationsCount[sum];
    }
}

**70. 爬楼梯 （进阶） **

这道题目 爬楼梯之前我们做过，这次再用完全背包的思路来分析一遍

代码随想录

import java.util.Scanner;

class ClimbStairs {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int maxSteps, climbers;
        while (scanner.hasNextInt()) {
            climbers = scanner.nextInt();
            maxSteps = scanner.nextInt();

            int[] dp = new int[maxSteps + 1];
            dp[0] = 1;
            for (int j = 1; j <= maxSteps; j++) {
                for (int i = 1; i <= climbers; i++) {
                    if (j - i >= 0) {
                        dp[j] += dp[j - i];
                    }
                }
            }
            System.out.println(dp[maxSteps]);
        }
    }
}