兑换零钱(一)

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

热度指数：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

奋斗的习习张

#
# 最少货币数
# @param arr int整型一维数组 the array
# @param aim int整型 the target
# @return int整型
#
class Solution:
    def minMoney(self , arr , aim ):
        # write code here
        # 因为货币面额都是大于1的，所以可以将dp全初始化为aim+1，也就是说兑换每个目标值
        # 都不会大于最大目标值，否则就是无法兑换
        dp = [aim + 1]*(aim+1)
        dp[0] = 0   # 兑换0元需要0张
        for i in range(1, aim + 1):  # 兑换i块钱需要的最少货币数
            for j in arr: # 每个货币的面额
                if j <= i:  # 如果货币面额比当前要兑换的目标小，就可以兑换。但是我们要
                    # 取最小的，所以需要遍历货币的所以面额。
                    # i - j表示用面额j兑换一张，所以后面要加1，dp[i-j]表示兑换完j后，剩余
                    # 货币需要的都最少货币数，这个是已知的，所以要比较最小值。
                    dp[i] = min(dp[i], dp[i - j] + 1)
        return dp[-1] if dp[-1] <= aim else -1

发表于 2021-08-29 20:49:19 回复(0)

Python

Keosu

class Solution:
    def minMoney(self , arr , aim ):
        arr.sort()
        a = {0}
        level = 0
        while True:
            if aim in a:
                return level
            if min(list(a)) > aim:
                return -1
            level += 1
            a = { x + y for y in a for x in arr}

编辑于 2021-07-13 23:02:37 回复(0)

Python

nlp_mon

def minMoney(self , arr , aim ):
# write code here
if not aim:
return 0
level =seen= {0}
res = 0
while level:
if aim in level:
return res
level = {a+c for a in level for c in arr if a+c <= aim}-seen
seen |= level
res += 1

return -1

发表于 2021-06-26 16:55:30 回复(0)