算法-leetcode-322. 零钱兑换

题目描述

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11

输出：3 
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3

输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

思路 【参考：代码随想录】

1. dp数组含义：凑成总金额i所需的最小硬币dp[i]个

2. 公式：dp[i] = min(dp[i-coin]+1, dp[i])

3. 初始化：dp[0] = 0 

4. 遍历顺序：外层for循环遍历硬币，内层for循环遍历金额【背包】

5. 打印数组：0，1，1，2，2，1 【coins = [1, 2, 5], amount = 5】

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        dp = [float('inf')] * (amount+1)
        dp[0] = 0
        for coin in coins:
            for i in range(coin, amount+1):
                if dp[i-coin] != float('inf'):
                    dp[i] = min(dp[i-coin]+1,dp[i])
        if dp[amount] == float('inf'):
            return -1
        return dp[amount]

if __name__=='__main__':
    s=Solution()
    coins = [1,2,5]
    amount = 5
    print(s.coinChange(coins, amount))