leetcode322 零钱兑换

叁歲伎倆 2023-06-15 12:26 134阅读 0赞

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

示例 1:

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

输入: coins = [2], amount = 3
输出: -1
说明:
你可以认为每种硬币的数量是无限的。

分析：最后一句话说明是什么背包类型了，直接一顿敲

不会的翻我的动态规划文章就行了。

  1. public class Solution {
  2.     public int coinChange(int[] coins, int amount) {
  3.         int max = amount + 1;             
  4.         int[] dp = new int[amount + 1];  
  5.         Arrays.fill(dp, max);  
  6.         dp[0] = 0;   
  7.         for (int i = 1; i <= amount; i++) {
  8.             for (int j = 0; j < coins.length; j++) {
  9.                 if (coins[j] <= i) {
  10.                     dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
  11.                 }
  12.             }
  13.         }
  14.         return dp[amount] > amount ? -1 : dp[amount];
  15.     }
  16. }

20191122152544430.png

发表评论

表情：
评论列表 （有 0 条评论，134人围观）

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

相关阅读

    相关 leetcode 322 零钱兑换

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

    ╰+攻爆jí腚メ╰+攻爆jí腚メ/ 0 赞/ 65 阅读

    相关 leetcode322 零钱兑换

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

    叁歲伎倆叁歲伎倆/ 0 赞/ 135 阅读

    相关 322. 零钱兑换

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

    忘是亡心i忘是亡心i/ 0 赞/ 352 阅读

    相关 Leetcode 322. 零钱兑换

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

    秒速五厘米秒速五厘米/ 0 赞/ 309 阅读

    相关 LeetCode-322. 零钱兑换

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

    小咪咪小咪咪/ 0 赞/ 356 阅读