[LeetCode]Coin Change 2

题目描述:

LeetCode 518. Coin Change 2

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

题目大意:

给定一些不同面值的硬币,和一个金钱总额。编写函数计算要得到目标金额,有多少种不同的硬币组合方式。

注意:你可以假设:

  1. 0 <= amount <= 5000
  2. 1 <= coin <= 5000
  3. 硬币个数不超过500
  4. 答案确保在32位整数范围内

解题思路:

动态规划(Dynamic Programmin)

状态转移方程见代码

Python代码:

class Solution(object):
    def change(self, amount, coins):
        """
        :type amount: int
        :type coins: List[int]
        :rtype: int
        """
        dp = [0] * (amount + 1)
        dp[0] = 1
        for c in coins:
            for x in range(c, amount + 1):
                dp[x] += dp[x - c]
        return dp[amount]

扩展思考:将上述代码中的循环顺序对调,即为求不同硬币的排列数(Permutation)

比如用面值{1, 2, 5}的硬币组成总额5元的不重复排列共9种,分别为:

[1,1,1,1,1] [1,1,1,2] [1,1,2,1] [1,2,1,1] [2,1,1,1] [1,2,2] [2,1,2] [2,2,1] [5]

Python代码:

class Solution(object):
    def change(self, amount, coins):
        """
        :type amount: int
        :type coins: List[int]
        :rtype: int
        """
        dp = [0] * (amount + 1)
        dp[0] = 1
        for x in range(amount + 1):
            for c in coins:
                if c > x: continue
                dp[x] += dp[x - c]
        return dp[amount]

 

本文链接:http://bookshadow.com/weblog/2017/02/12/leetcode-coin-change-2/
请尊重作者的劳动成果,转载请注明出处!书影博客保留对文章的所有权利。

如果您喜欢这篇博文,欢迎您捐赠书影博客: ,查看支付宝二维码