[LeetCode] 322. Coin Change

ccj659 发布于2019-08-16 13:37 / 3208人阅读

Problem

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2:

Input: coins = [2], amount = 3
Output: -1
Note:
You may assume that you have an infinite number of each kind of coin.

Solution

class Solution {
    public int coinChange(int[] coins, int n) {
        if (n < 1) return 0;
        int[] dp = new int[n+1]; 
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int coin : coins) {
            for (int i = coin; i <= n; i++) {
                if (dp[i - coin] != Integer.MAX_VALUE) {
                    dp[i] = Math.min(dp[i], dp[i-coin] + 1);
                }
            }
        }
        return dp[n] == Integer.MAX_VALUE ? -1 : dp[n];
    }
}

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/72037.html

leetcode322. Coin Change

摘要：传入的参数为手上有的纸币的面额以及希望兑换的面额。这里假设纸币的数量是无穷的。这题本质上考察的是动态规划思想。这里有两种动态规划的方法，分别从递归和非递归的角度解决这个问题。具体的情况还是要看数据的分布情况来确定选择哪种方法。题目要求 You are given coins of different denominations and a total amount of money ...

kohoh_ 2019-08-15 14:41 评论0 收藏0
[LeetCode - Dynamic Programming] Coin Change

摘要：解题思路动态规划，用表示总价为的最小纸币张数，很容易想到状态转移方程当然前提是要大于纸币金额数。表示取一张面额加上合计为的最小纸币数。另题目要求无法合计出的金额，要返回，所以要作特殊处理，否则就会返回元素初始化值代码 Coin ChangeYou are given coins of different denominations and a total amount of money...

dackel 2019-08-16 10:26 评论0 收藏0
[LeetCode] 518. Coin Change 2

Problem You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infini...

stefan 2019-08-16 13:44 评论0 收藏0
LeetCode 精选TOP面试题【51 ~ 100】

摘要：有效三角形的个数双指针最暴力的方法应该是三重循环枚举三个数字。总结本题和三数之和很像，都是三个数加和为某一个值。所以我们可以使用归并排序来解决这个问题。注意因为归并排序需要递归，所以空间复杂度为 ...

Clect 2021-11-15 11:38 评论0 收藏0
100块钱换零钱，最多有多少种方式的 JavaScript 版本实现

摘要：原文链接欢迎现在有块钱人民币，将块钱换成零钱最小币值元，一共有多少方式总的不同方式的数目等于将现金数换成除第一种币值之外的所有其他硬币的不同方式数据，加上将现金数第一种币值换成所有种类的币值的不同方式，根据上面的说法来实现吧实现中的是中的原文链接: 欢迎 Star 现在有100块钱人民币，将 100 块钱换成零钱（最小币值 1 元），一共有多少方式？总的不同方式的数目等于：将现...

xeblog 2019-08-22 10:49 评论0 收藏0