Daily LeetCode 322. Coin Change

https://leetcode.com/problems/coin-change/

Medium

问题描述：

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:

Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

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

题目分析：

给定硬币种类，我们需要找出最少的硬币数达成目标和。

这一题我最先想到的解法是暴力解法，但会导致超时。这种类型的题目，动态规划是一个好的选择。设置一个长度为amount + 1的数组dp，dp[i]表示以当前的硬币种类，达成目标和i所需的最少硬币数。dp[i] = min(dp[i], d[i - coin] + 1)，coin是所有小于当前和的硬币值。

以Example 1为例，amount = 11，我们设置一个长度为12的数组，这个动态规划数组在遍历过程中的值变化如下，其中，inf为无穷大：

dp:[0, 1, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]
dp:[0, 1, 1, inf, inf, inf, inf, inf, inf, inf, inf, inf]
dp:[0, 1, 1, 2, inf, inf, inf, inf, inf, inf, inf, inf]
dp:[0, 1, 1, 2, 2, inf, inf, inf, inf, inf, inf, inf]
dp:[0, 1, 1, 2, 2, 1, inf, inf, inf, inf, inf, inf]
dp:[0, 1, 1, 2, 2, 1, 2, inf, inf, inf, inf, inf]
dp:[0, 1, 1, 2, 2, 1, 2, 2, inf, inf, inf, inf]
dp:[0, 1, 1, 2, 2, 1, 2, 2, 3, inf, inf, inf]
dp:[0, 1, 1, 2, 2, 1, 2, 2, 3, 3, inf, inf]
dp:[0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, inf]
dp:[0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]

代码：

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        dp = [0] + [float('inf')] * amount

        for i in range(1, amount + 1):
            for coin in coins:
                if coin <= i:
                    dp[i] = min(dp[i], dp[i - coin] + 1)

        return -1 if dp[amount] == float('inf') else dp[amount]