LeetCode : 518. Coin Change 2凑硬币

不念不忘少年蓝@ 2021-06-24 16:12 374阅读 0赞

**试题**

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 infinite number of each kind of coin.
    
     
    
    Example 1:
    
    Input: amount = 5, coins = [1, 2, 5]
    Output: 4
    Explanation: there are four ways to make up the amount:
    5=5
    5=2+2+1
    5=2+1+1+1
    5=1+1+1+1+1
    Example 2:
    
    Input: amount = 3, coins = [2]
    Output: 0
    Explanation: the amount of 3 cannot be made up just with coins of 2.
    Example 3:
    
    Input: amount = 10, coins = [10] 
    Output: 1
     
    
    Note:
    
    You can assume that
    
    0 <= amount <= 5000
    1 <= coin <= 5000
    the number of coins is less than 500
    the answer is guaranteed to fit into signed 32-bit integer

**代码**  
这一题明显动归， 但是循环嵌套很有技巧。如果我们把amount放在外循环，就会出现重复统计的情况，而把coins放在外部循环就能很好避免这种情况。

class Solution {
        public int change(int amount, int[] coins) {
            int[] dp = new int[amount+1];
            dp[0] = 1;
            
            for(int coin : coins) {
                for(int i = 1; i <= amount; i++) {
                    if(i - coin >=0) {
                        dp[i] += dp[i-coin]; 
                    }
                }
            }
            return dp[amount];
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode - Medium - 322. Coin Change

Topic Dynamic Programming Description [https://leetcode.com/problems/coin-chan

谁践踏了优雅/ 2022年12月31日 13:20/ 0 赞/ 136 阅读

相关凑硬币问题

/ 给出k中面值的硬币，每种硬币的数量无限，再给一个总金额amount，问最少需要几枚硬币凑出这个金额，如果凑不出，返回-1 dp[i]定义：当目标金额为i时，至少

迷南。/ 2022年10月27日 13:54/ 0 赞/ 181 阅读

相关 leetcode 518. Coin Change 2 | 518. 零钱兑换 II（暴力递归-＞傻缓存-＞动态规划）

题目 [https://leetcode.com/problems/coin-change-2/][https_leetcode.com_problems_coin-ch

秒速五厘米/ 2022年09月12日 03:50/ 0 赞/ 207 阅读

相关 leetcode 322 Coin Change

You are given coins of different denominations and a total amount of money amount. Write

绝地灬酷狼/ 2022年08月20日 10:30/ 0 赞/ 7 阅读

相关 [leetcode] 518. Coin Change 2 -- JavaScript 代码【动态规划】

var change = function(amount, coins) { var dpArray = []; for(let i=

不念不忘少年蓝@/ 2022年06月18日 05:10/ 0 赞/ 83 阅读

相关 leetcode 518. Coin Change 2 类似背包问题 + 很简单的动态规划DP解决

You are given coins of different denominations and a total amount of money. Write a func

迈不过友情╰/ 2022年06月03日 03:13/ 0 赞/ 143 阅读

相关 LeetCode：322. Coin Change（硬币兑换问题）

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如

左手的ㄟ右手/ 2022年04月03日 15:54/ 0 赞/ 186 阅读

相关 leetcode [322]Coin Change

You are given coins of different denominations and a total amount of money amount. Write

小咪咪/ 2021年12月07日 14:21/ 0 赞/ 234 阅读

相关 LeetCode : 518. Coin Change 2凑硬币

试题 You are given coins of different denominations and a total amount of money. Writ

不念不忘少年蓝@/ 2021年06月24日 16:12/ 0 赞/ 375 阅读

相关 LeetCode : 322. Coin Change 凑齐硬币

试题 You are given coins of different denominations and a total amount of money amount.

￡神魔★判官ぃ/ 2021年06月24日 16:11/ 0 赞/ 348 阅读