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

【算法-动态规划】零钱兑换 II-力扣 518

💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。
img

  • 推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老
  • 导航
    • 檀越剑指大厂系列:全面总结 java 核心技术点,如集合,jvm,并发编程 redis,kafka,Spring,微服务,Netty 等
    • 常用开发工具系列:罗列常用的开发工具,如 IDEA,Mac,Alfred,electerm,Git,typora,apifox 等
    • 数据库系列:详细总结了常用数据库 mysql 技术点,以及工作中遇到的 mysql 问题等
    • 懒人运维系列:总结好用的命令,解放双手不香吗?能用一个命令完成绝不用两个操作
    • 数据结构与算法系列:总结数据结构和算法,不同类型针对性训练,提升编程思维,剑指大厂

非常期待和您一起在这个小小的网络世界里共同探索、学习和成长。💝💝💝 ✨✨ 欢迎订阅本专栏 ✨✨

博客目录

        • 1.题目
        • 2.示例
        • 3.二维
        • 4.一维

1.题目

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

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

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

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

2.示例

示例 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

示例 2:

输入:amount = 3, coins = [2]
输出:0
解释:只用面额 2 的硬币不能凑成总金额 3 。

示例 3:

输入:amount = 10, coins = [10]
输出:1
3.二维
public class DP_07_ChangeMakingProblemLeetcode518_02 {public int change(int[] coins, int amount) {int[][] dp = new int[coins.length][amount + 1];for (int i = 0; i < coins.length; i++) {dp[i][0] = 1;}for (int j = 1; j < amount + 1; j++) {if (j >= coins[0]) {dp[0][j] = dp[0][j - coins[0]];}}print(dp);for (int i = 1; i < dp.length; i++) {for (int j = 1; j < amount + 1; j++) {if (j >= coins[i]) {dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]];}else {dp[i][j] = dp[i - 1][j];}}}print(dp);return dp[coins.length - 1][amount];}public static void main(String[] args) {DP_07_ChangeMakingProblemLeetcode518_02 leetcode = new DP_07_ChangeMakingProblemLeetcode518_02();int count = leetcode.change(new int[]{1, 2, 5}, 5);
//        int count = leetcode.change(new int[]{2}, 3);
//        int count = leetcode.change(new int[]{15, 10, 1}, 21);
//        int count = leetcode.change(new int[]{25, 10, 5, 1}, 41);System.out.println(count);}static void print(int[][] dp) {System.out.println(StringUtil.repeat("-", (18)));for (int[] d : dp) {final Object[] array = Arrays.stream(d).boxed().toArray();System.out.printf((StringUtil.repeat("%2d ", d.length) + "%n"), array);}}
}
4.一维
public class ChangeMakingProblemLeetcode518 {/*面值    0        1        2        3        4        51    1        1        1        1        1        12    1        1        2        2        3        35    1        1        2        2        3        4面值    0        1        2        31        0        0        02    1        0        1        0*/public int change(int[] coins, int amount) {int[] dp = new int[amount + 1];dp[0] = 1;for (int coin : coins) {for (int j = coin; j < amount + 1; j++) {dp[j] = dp[j] + dp[j - coin];}}return dp[amount];}public static void main(String[] args) {ChangeMakingProblemLeetcode518 leetcode = new ChangeMakingProblemLeetcode518();int count = leetcode.change(new int[]{1, 2, 5}, 5);System.out.println(count);}}

觉得有用的话点个赞 👍🏻 呗。
❤️❤️❤️本人水平有限,如有纰漏,欢迎各位大佬评论批评指正!😄😄😄

💘💘💘如果觉得这篇文对你有帮助的话,也请给个点赞、收藏下吧,非常感谢!👍 👍 👍

🔥🔥🔥Stay Hungry Stay Foolish 道阻且长,行则将至,让我们一起加油吧!🌙🌙🌙

img

http://www.lryc.cn/news/194756.html

相关文章:

  • Hadoop3教程(六):HDFS中的DataNode
  • Macos音乐制作:Ableton Live 11 Suite for Mac中文版
  • ThinkPHP5小语种学习平台
  • 升级包版本之后Reflections反射包在springboot jar环境下扫描不到class排查过程记录
  • Excel 函数大全应用,包含各类常用函数
  • 深入浅出的介绍一下虚拟机VMware Workstation——part3(VMware快照)
  • 《Python基础教程》专栏总结篇
  • JavaScript 事件
  • 轻松学会这招,给大量视频批量添加滚动字幕不求人
  • 哪个文字转语音配音软件最好用?
  • 多关键词高亮显示
  • 浅谈 33 台 iPad 发展史;OpenAI“悄悄”修改了企业核心价值观丨 RTE 开发者日报 Vol.67
  • Mysql之备份(Mysqldump)
  • 算法leetcode|84. 柱状图中最大的矩形(rust重拳出击)
  • Java中通过List中的stream流去匹配相同的字段去赋值,避免for循环去查询数据库进行赋值操作
  • 开源酒店预订订房小程序源码系统+多元商户 前端+后端完整搭建教程 可二次开发
  • Leetcode 2906. Construct Product Matrix
  • 【Leetcode Sheet】Weekly Practice 11
  • 本地PHP搭建简单Imagewheel私人云图床,在外远程访问
  • Python图像处理进阶:Pillow库的中级应用
  • 多线程怎么共用一个事务
  • scrollIntoView使用与属性详解
  • 【LeetCode热题100】--169.多数元素
  • LeetCode 面试题 10.01. 合并排序的数组
  • 揭秘OLED透明拼接屏的参数规格:分辨率、亮度与透明度全解析
  • 竞赛选题 深度学习YOLOv5车辆颜色识别检测 - python opencv
  • linux U盘无法使用,提示“Partition table entries are not in disk order“
  • HDLbits: Fsm ps2
  • 【设计模式】八、桥接模式
  • 从零开始的stable diffusion