兑换零钱(一)

[编程题]兑换零钱(一)

热度指数：91828 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。

如果无解，请返回-1.

数据范围：数组大小满足 $0 \le n \le 10000$ ，数组中每个数字都满足 $0 < val \le 10000$ ， $0 \le aim \le 5000$

要求：时间复杂度 $O(n \times aim)$ ，空间复杂度 $O(aim)$ 。

示例1

输入

[5,2,3],20

输出

示例2

输入

[5,2,3],0

输出

示例3

输入

[3,5],2

输出

-1

备注:

算法知识视频讲解

Python 3

Vivimore

class Solution:
    def minMoney(self , arr: List[int], aim: int) -> int:
        dp = [aim+1 for i in range(aim+1)]
        dp[0] = 0
        for i in range(1, aim+1):
            for j in arr:
                if i >= j:
                    dp[i] = min(dp[i], dp[i-j]+1)
        return dp[aim] if dp[aim] < aim+1 else -1

发表于 2022-05-22 14:34:12 回复(0)

Python 3

danspace

class Solution:
    def minMoney(self , arr: List[int], aim: int) -> int:
        # write code here
        aim_list = [aim+1]*(aim+1)
        aim_list[0] = 0
        for i in range(1, aim+1):
            for j in arr:
                if j <= i:
                    # 可以找零
                    aim_list[i] = min(aim_list[i], aim_list[i-j]+1)
        if aim_list[aim] == aim+1:
            # 无法找零
            return -1
        return aim_list[aim]

发表于 2022-04-19 18:59:31 回复(0)

Python 3

Joy_9

class Solution:
    def minMoney(self , arr: List[int], aim: int) -> int:
        # write code here
        #d[i]=min(d[i1],d[i2],d[d3])+1
        #d[20]=min(d[15],d[18],d[17])+1
        dp=[float("Inf")]*(aim+1)
        dp[0]=0
        for coin in arr:
            for i in range(coin,aim+1):
                dp[i]=min(dp[i],dp[i-coin]+1)
        return dp[aim] if dp[aim]!=float("Inf") else -1

发表于 2022-01-08 07:55:11 回复(0)

Python 3

VincentLau~

class Solution:
    def minMoney(self , arr , aim ):
        # write code here
        dp = [float("inf")]*(aim+1)
        dp[0] = 0
        for i in range(len(arr)):
            for j in range(arr[i], aim+1):
                dp[j] = min(dp[j], dp[j-arr[i]]+1)
        return dp[-1] if dp[-1] != float('inf') else -1

完全背包

发表于 2021-08-14 22:21:02 回复(0)