322.零钱兑换

322.零钱兑换

文章目录

• • • 题目
    • 思路
    • 易错点
    • 代码
    • 运行过程
    • 代码2
    • 运行结果2

题目

'''
Description: 322.零钱兑换
Autor: 365JHWZGo
Date: 2021-12-02 11:28:21
LastEditors: 365JHWZGo
LastEditTime: 2021-12-02 15:49:39
'''

思路

直观解题思路:
        是多重背包问题，可以无限次拿物品，拿到的话返回最小值个数，否则返回-1

思路:
        1.确定dp数组及其含义
            dp[j]表示在amount为j时所需要的最小coin数
        2.确定递推公式
            dp[j]=dp[j-coins[i]]+1，在此处需要确定是哪一个coins[i],因此需要判断在容量为j时是coins数组中的哪一个硬币所构成的j数量最少
        3.初始化dp数组
        	初始化为0
        4.确定遍历顺序
        	先遍历容量，在遍历coins，这样可以保证coins里的数是排序数，内循环从小到大
        5.举例推导
        	略

易错点

这道题不能单纯的使用nums[j]=min(nums[j-coins[i]]+1,nums[j])，因为在初始化时的最小值是0，除非将初始化为10001【因为最大amount=10000，最小coins[i]=1】，此时赋值nums[0]=0

代码

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        nums = [0 for _ in range(amount+1)]
        s = 10001

        for j in range(1, amount+1):
            for i in range(len(coins)):
                if j >= coins[i]:
                    temp = nums[j-coins[i]]+1
                    if temp < s:
                        s = temp
            nums[j] = s
            s = 100001
        if nums[-1]>10000:
            return -1
        else:
            return nums[-1]

运行过程

代码2

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        nums = [10001 for _ in range(amount+1)]
        nums[0]=0

        for j in range(1, amount+1):
            for i in range(len(coins)):
                if j >= coins[i]:
                    nums[j]=min(nums[j],nums[j-coins[i]]+1)
        # print(nums)
        if nums[-1]>10000:
            return -1
        else:
            return nums[-1]

运行结果2