代码随想录day44-Toy模板网

这篇具有很好参考价值的文章主要介绍了代码随想录day44。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

完全背包

其实就是每个物品可以使用无数次，给我们一个容器，装满这个容器的最大价值是多少。

思路：
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。

完全背包的组合和排序

518. 零钱兑换 II

题目

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

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

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

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

示例 1：

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1文章来源地址https://www.toymoban.com/news/detail-416057.html

class Solution {
    public int change(int amount, int[] coins) {

        // dp[i] 表示i的情况下有多少种
        // dp[i]
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for(int i = 0;i < coins.length;i++){
            for(int j = coins[i];j <= amount; j++){
                dp[j] += dp[j - coins[i]];
            }
        }
        return dp[amount];

    }
}

377. 组合总和 Ⅳ

class Solution {
    public int combinationSum4(int[] nums, int target) {

        int[] dp = new int[target + 1];
        dp[0] =1;
        // 纯完全背包：是为了求最大价值
        // 完全背包的组合：先weight后顺序
        // for(int i = 0;i < nums.length;i ++){
        //     for(int j = nums[i];j <= target;j++){
        //         dp[j] += dp[j - nums[i]];    //排列
         //     }
        // }
        for(int j = 0;j <= target;j++){
            for(int i = 0;i < nums.length;i++){
                if(j >= nums[i]){
                    dp[j] += dp[j - nums[i]];
                }
            }
        }
        return dp[target];

    }
}