题目描述：

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.

题目大意：

给定不同面值的硬币和金额总值。编写函数计算凑齐金额总值最少需要的硬币数目。如果不可能凑齐指定的金额，返回-1。

测试用例如题目描述。

注意：

你可以假设每种面值的硬币数目都是无穷的。

解题思路：

解法I：动态规划（Dynamic Programming）

状态转移方程：

dp[x + c] = min(dp[x] + 1, dp[x + c])

其中dp[x]代表凑齐金额x所需的最少硬币数，c为可用的硬币面值

初始令dp[0] = 0

贪心算法是不正确的，因为有可能会错过全局最优解。

Python代码：

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

解法II：广度优先搜索（BFS）

参考：https://leetcode.com/discuss/76432/fast-python-bfs-solution

将问题转化为求X轴0点到坐标点amount的最短距离（每次向前行进的合法距离为coin的面值）

Python代码：

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        steps = collections.defaultdict(int)
        queue = collections.deque([0])
        steps[0] = 0
        while queue:
            front = queue.popleft()
            level = steps[front]
            if front == amount:
                return level
            for c in coins:
                if front + c > amount:
                    continue
                if front + c not in steps:
                    queue += front + c,
                    steps[front + c] = level + 1
        return -1

 

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

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