当前位置: 首页 > article >正文

代码随想录算法训练营第四十四天| 518. 零钱兑换 II、377. 组合总和 Ⅳ。

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
  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • coins 中的所有值 互不相同
  • 0 <= amount <= 5000

总结:

        本题要根据不同的硬币去凑大小为amount的金额数,查看所有凑成总金额的硬币组合数,每个面的硬币有无限个,这就是完全背包问题,,区别于01背包,所有的面额有无数个,可以随便去,当时我们的内循环,j也就是背包大小,之所以逆序来循环,就是为了避免前面的硬币能重复取得问题,故这里我们可以重复取,所以内循环j也是正序遍历即可。

class Solution {
    public int change(int amount, int[] coins) {
        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. 组合总和 Ⅳ

题目链接:力扣

题目要求:

        给你一个由 不同 整数组成的数组 nums ,和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。题目数据保证答案符合 32 位整数范围。

示例 1:

输入:nums = [1,2,3], target = 4
输出:7
解释:
所有可能的组合为:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意,顺序不同的序列被视作不同的组合。
  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 1000
  • nums 中的所有元素 互不相同
  • 1 <= target <= 1000

总结:

        这里所说的组合,说的是顺序不同的序列被视作不同的组合,所以这里指的是从nums中找出并返回总和为target的元素序列的个数,这是找排列,不是找组合,这里nums中的每个元素也能重复取,故是完全背包问题,求排列的话,需要将循环顺序来颠倒,外循环为背包,内循环为物品,

比如,示例一中,如果外循环物品内循环背包,就不可能出现(1, 2, 1)、(2, 1, 1)、(3, 1)这三种情况,因为物品1已经在第一次外循环中穷尽了,1只能出现在2,3的前面,不能出现在2,3的后面,但是外循环背包,内循环物品却可以避免这种情况。其实这里还不是特别理解,先记住遇到排列问题,就外循环背包,内循环物品,又是物品能随意取得问题,故背包也是正序遍历即可。

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 = 0;i < nums.length;i++){
                if(j >= nums[i]){
                    dp[j] += dp[j - nums[i]];
                }
            }
        }
        return dp[target];
    }
}

http://www.kler.cn/a/6486.html

相关文章:

  • 设计模式期末复习
  • 《Java核心技术I》Swing的滑动条
  • Python tkinter写的《电脑装配单》和 Html版 可打印 可导出 excel 文件
  • day12
  • 免费送源码:Java+ssm++MVC+HTML+CSS+MySQL springboot 社区医院信息管理系统的设计与实现 计算机毕业设计原创定制
  • 厦门凯酷全科技有限公司短视频带货可靠吗?
  • AJAX在PHP中的应用示例代码
  • Python垃圾回收机制详解
  • 研报精选230405
  • taro之--使用nutui
  • 【新2023Q2模拟题JAVA】华为OD机试 - 矩阵最值 or 计算二维矩阵的最大值
  • 如何实现接口调用的重试
  • RocketMQ消息文件过期原理
  • 面试官:谈谈你对MySQL事务的理解
  • 初识设计模式 - 适配器模式
  • 【python设计模式】8、桥接模式
  • Python入门教程+项目实战-7.2节: 循环控制结构
  • 【Python入门第四十二天】Python丨NumPy 数组裁切
  • 自定义starter
  • 【Ruby学习笔记】4.Ruby 类和对象及类案例
  • OBProxy 路由策略与使用运维-常见问题
  • FIFO的工作原理及其设计
  • 哈利波特c++千行代码
  • C语言程序环境和预处理
  • USB抓包分析
  • Spring Security