322. 零钱兑换

忘是亡心i 2022-10-09 12:17 218阅读 0赞

> 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
> 
> 你可以认为每种硬币的数量是无限的。
> 
> 示例 1：
> 
> 输入：coins = \[1, 2, 5\], amount = 11  
> 输出：3   
> 解释：11 = 5 + 5 + 1  
> 示例 2：
> 
> 输入：coins = \[2\], amount = 3  
> 输出：-1

**背包问题模板**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70][]

class Solution {
        public int coinChange(int[] coins, int amount) {
            /**
            开一个数组记录当前价格最少使用多少硬币i
             */
             int dp[]=new int [amount+1];
             Arrays.fill(dp,999);
             dp[0]=0;
             for(int i=0;i<=amount;i++){
                 for(int j=0;j<coins.length;j++){
                     if(i-coins[j]>=0){
                         dp[i]=Math.min(dp[i],dp[i-coins[j]]+1);//1 不拿当前的硬币  用当前的硬币  硬币数+1
                     }
                 }
             }
             return dp[amount]==999?-1:dp[amount];
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTQzNDkwMg_size_16_color_FFFFFF_t_70]: /images/20221005/b30d2ee1b76d4345bafa886633d3ca6f.png

发表评论取消回复

表情：

评论列表（有 0 条评论，218人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode322.零钱兑换

//322.零钱兑换 if 0 /* 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额...

小灰灰/ 2024年04月18日 08:24/ 0 赞/ 91 阅读

相关 LeetCode-322.零钱兑换

目录题目思路回溯法动态规划动态规划(压缩) 题目来源 [322. 零钱兑换][322.] 题目思路

朱雀/ 2024年03月25日 19:39/ 0 赞/ 78 阅读

相关 322. 零钱兑换

322. 零钱兑换题干分析解题思路 1. 确定dp数组以及下标的含义 2. 确定递推公式 3. dp数组如何初始化

阳光穿透心脏的1/2处/ 2023年10月16日 17:04/ 0 赞/ 18 阅读

相关 322. 零钱兑换

题目： [322. 零钱兑换][322.] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_tex

╰半夏微凉°/ 2023年07月13日 05:57/ 0 赞/ 29 阅读

相关 Leetcode 322. 零钱兑换

Leetcode 322. 零钱兑换 1、问题分析 2、问题解决 3、总结 1、问题分析题目链接：[https://leetcode-cn.c

曾经终败给现在/ 2023年02月14日 03:06/ 0 赞/ 47 阅读

相关 322. 零钱兑换

> 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。 >

忘是亡心i/ 2022年10月09日 12:17/ 0 赞/ 219 阅读

相关 LeetCode：322. 零钱兑换

链接：[https://leetcode-cn.com/problems/coin-change/][https_leetcode-cn.com_problems_coin-c

今天药忘吃喽~/ 2022年10月06日 06:55/ 0 赞/ 214 阅读

相关 Leetcode 322. 零钱兑换

题目重述给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何

秒速五厘米/ 2022年09月11日 15:18/ 0 赞/ 213 阅读

相关 LeetCode-322. 零钱兑换

[322. 零钱兑换][322.] 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币

小咪咪/ 2022年01月27日 00:25/ 0 赞/ 242 阅读

相关 322.零钱兑换

//给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 // -1

淩亂°似流年/ 2021年06月22日 15:38/ 0 赞/ 397 阅读