[LeetCode] 518. Coin Change 2

stefan 发布于2019-08-16 13:44 / 1402人阅读

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 infinite number of each kind of coin.

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

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

Solution DP

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];
    }
}

DFS - TLE

class Solution {
    int count = 0;
    public int change(int amount, int[] coins) {
        if (amount == 0) return 1;
        dfs(coins, 0, 0, amount);
        return count;
    }
    private void dfs(int[] coins, int start, int sum, int amount) {
        if (start == coins.length) return;
        if (sum == amount) {
            count++;
            return;
        }
        for (int i = start; i < coins.length; i++) {
            if (coins[i] + sum > amount) continue;
            else dfs(coins, i, sum+coins[i], amount);
        }
    }
}

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

转载请注明本文地址：https://www.ucloud.cn/yun/72246.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] 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
100块钱换零钱，最多有多少种方式的 JavaScript 版本实现

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

xeblog 2019-08-22 10:49 评论0 收藏0
koa2开发微信公众号: 不定期推送最新币圈消息

摘要：背景比特币说好的分叉最后却分叉不成，如今算力又不够，于是比特现金想篡位没一个星期就涨了快倍，错过这趟快车甚是后悔，于是打算写一个可不定期推送最新消息的微信公众号。既然是利用微信这个平台载体，当然要熟悉微信的，遂封装了一下。背景：比特币说好的segwit2x分叉最后却分叉不成，如今算力又不够，于是比特现金想篡位? 没一个星期就涨了快10倍，错过这趟快车甚是后悔，于是打算写一个可不定期推...

xi4oh4o 2019-06-27 18:12 评论0 收藏0