322. 零钱兑换

忘是亡心i 2022-10-09 12:17 326阅读 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

  1. class Solution {
  2. public int coinChange(int[] coins, int amount) {
  3. /**
  4. 开一个数组记录当前价格最少使用多少硬币i
  5. */
  6. int dp[]=new int [amount+1];
  7. Arrays.fill(dp,999);
  8. dp[0]=0;
  9. for(int i=0;i<=amount;i++){
  10. for(int j=0;j<coins.length;j++){
  11. if(i-coins[j]>=0){
  12. dp[i]=Math.min(dp[i],dp[i-coins[j]]+1);//1 不拿当前的硬币 用当前的硬币 硬币数+1
  13. }
  14. }
  15. }
  16. return dp[amount]==999?-1:dp[amount];
  17. }
  18. }

发表评论

表情:
评论列表 (有 0 条评论,326人围观)

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

相关阅读

    相关 322. 零钱兑换

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

    相关 Leetcode 322. 零钱兑换

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

    相关 LeetCode-322. 零钱兑换

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

    相关 322.零钱兑换

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