leetcode322. Coin Change

kohoh_ 发布于2019-08-15 14:41 / 997人阅读

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

题目要求

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:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Note:
You may assume that you have an infinite number of each kind of coin.

这里模拟实现了一个换钱算法。传入的参数为手上有的纸币的面额以及希望兑换的面额。这里假设纸币的数量是无穷的。

这题本质上考察的是动态规划思想。这里有两种动态规划的方法，分别从递归和非递归的角度解决这个问题。具体的情况还是要看数据的分布情况来确定选择哪种方法。

非递归

这里我们新建一个临时数组result，下标i上的值来存储用当前手上的纸币兑换面额i时所需要的最少的纸币数量。这样，假设有一个纸币数组[coin[0], coint[1], ..., coin[k]]，我们需要计算兑换面额i所需要的最小数量的纸币，那么只需要比较[result[i-coin[0]], result[i-coin[1]], result[i-coin[2]] ... , result[i-coint[k]]]即可。这里需要考虑一些越界情况比如手上纸币面额比需兑换面额大。还有可能result[i-coin[t]]是无法兑换的。

    public int coinChange(int[] coins, int amount) {
        if(amount==0) return 0;
        Arrays.sort(coins);
        if(coins==null || coins.length==0 || amount < coins[0]) return -1;
        int[] result = new int[amount+1];
        for(int i = coins[0] ; i<=amount; i++){
            int tmp = Integer.MAX_VALUE;
            for(int j = 0 ; j
递归
这里需要注意的是，用int数组作为一个缓存来减少重复计算的损耗。其实这里的代码还是可以继续优化的。
    private int[] cache;
    public int coinChange2(int[] coins, int amount){
        cache = new int[amount];
        return coinChangeRecursive(coins, amount);
    }
    
    public int coinChangeRecursive(int[] coins, int amount){
        if(amount<0) return -1;
        if(amount==0) return 0;
        if(cache[amount-1] != 0) return cache[amount-1];
        int min = Integer.MAX_VALUE;
        for(int coin : coins){
            int res = coinChangeRecursive(coins, amount-coin);
            if(res>=0 && res

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

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

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

[LeetCode] 322. Coin Change

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 o...

ccj659 2019-08-16 13:37 评论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