首页 > 其他分享 >动态规划03——322. 零钱兑换

动态规划03——322. 零钱兑换

时间:2023-04-13 11:35:52浏览次数:46  
标签:03 示例 int coins 322 零钱 amount 硬币 dp

322. 零钱兑换

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

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1

你可以认为每种硬币的数量是无限的。

示例 1:

输入:coins = [1, 2, 5], amount = 11
输出:3 
解释:11 = 5 + 5 + 1

示例 2:

输入:coins = [2], amount = 3
输出:-1

示例 3:

输入:coins = [1], amount = 0
输出:0

提示:

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 231 - 1
  • 0 <= amount <= 104

方法:动态规划

class Solution {
    int coinChange(int[] coins, int amount) {
        
        int[] dp = new int[amount+1];
        // 数组大小为 amount + 1,初始值也为 amount + 1
        Arrays.fill(dp,amount+1);

        // base case
        dp[0] = 0;

        // 外层 for 循环在遍历所有状态的所有取值
        for (int i =0; i < amount+1;++i) {
            // 内层 for 循环在求所有选择的最小值
            for (int coin : coins) {
                // 子问题无解,跳过
                if (i - coin < 0) continue;
                dp[i] = Math.min(dp[i],1+dp[i-coin]);
            }
        }

        return dp[amount] == amount+1 ? -1 : dp[amount];
    }
}

 

标签:03,示例,int,coins,322,零钱,amount,硬币,dp
From: https://www.cnblogs.com/fulaien/p/17312856.html

相关文章

  • L1-033 出生年
    一、问题描述  以上是新浪微博中一奇葩贴:“我出生于1988年,直到25岁才遇到4个数字都不相同的年份。”也就是说,直到2013年才达到“4个数字都不相同”的要求。本题请你根据要求,自动填充“我出生于y年,直到x岁才遇到n个数字都不相同的年份”这句话。输入格式:输入在一行中给出出......
  • 同样的文件用'du'、'ls -l'与'ls -s'查看大小不同
    清空文件的几种方式>access.logcat/dev/null>access.logddif=/dev/nullof=access.logddif=/dev/zeroof-access.logbs=1024count=2为什么同样的文件在不同的文件系统中大小不一样?'du'、'ls-l'与'ls-s'的区别辨析磁盘告警之---神奇的魔法(Sparsefile)......
  • 【LeeCode】1035. 不相交的线
    【题目描述】在两条独立的水平线上按给定的顺序写下 nums1 和 nums2 中的整数。现在,可以绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线,这些直线需要同时满足满足: nums1[i]==nums2[j]且绘制的直线不与任何其他连线(非水平线)相交。请注意,连线即使在端点也不能相交:每个......
  • 003.方差&回归分析以及pandas数据分析流程
    一、方差分析   二、回归分析 三、案例讲解 ......
  • Python程序笔记20230304
    抛硬币实验random模块importrandomrandom.randint(a,b)返回一个随机整数N,范围是:a<=N<=brandom.choice("ilovefishc")从"ilovefishc"这个字符串中随机选出一个字符。编写一个双色球的开奖模拟程序importrandomred=random.sample(range(1,34),6)blue=r......
  • Can't open dsw file in Visual Studio C++ 6.0
    Can'topendswfileinVisualStudioC++6.0 WhenItryto"OpenWorkplace"ofmyproject,visualstudiodoesnothing,solutionexplorerisempty.AlsowhenItrytoopenmyproject,Ioccasionallyseethiserror:Thismakefilewas......
  • UVa 103 Stacking Boxes (DP&DAG)
    103-StackingBoxesTimelimit:3.000secondshttp://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=114&page=show_problem&problem=39BackgroundSomeconceptsinMathematicsandComputerSciencearesimpleinoneortw......
  • UVa 10041 Vito's Family (中位数&快速选择)
    10041-Vito'sFamilyTimelimit:3.000secondshttp://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=982BackgroundTheworld-knowngangsterVitoDeadstoneismovingtoNewYork.He......
  • UVa 10344 23 out of 5 (全排列枚举&回溯)
    10344-23outof5Timelimit:3.000secondshttp://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1285Yourtaskistowriteaprogramthatcandecidewhetheryoucanfindanarithmetic......
  • springcloud gateway根据服务名称进行路由失败There was an unexpected error (type=S
    出现错误,如下图:解决办法:检查自己的yaml文件:server:port:88spring:application:name:applicationNamecloud:nacos:discovery:server-addr:127.0.0.1:8848gateway:#开启服务发现路由(不开启跨域问题可能无法解决)disco......