换钱的最少货币数

[编程题]换钱的最少货币数

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

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

输入描述:

输入包括两行，第一行两个整数n（0<=n<=1000）代表数组长度和aim（0<=aim<=5000），第二行n个不重复的正整数，代表arr。

输出描述:

输出一个整数，表示组成aim的最小货币数，无解时输出-1.

示例1

输入

3 20
5 2 3

输出

说明

20=5*4

示例2

输入

3 0
5 2 3

输出

示例3

输入

2 2
3 5

输出

-1

备注:

时间复杂度，空间复杂度。

算法知识视频讲解

Python

牛客640734838号

n,m=input().split()
l=list(map(int,input().split()))
n=int(n)
m=int(m)
l.sort()

def fun(n,m,l):
    if m==0:
        return 0
    if m<l[0]:
        return -1

    dp=[0 for i in range(m+1)]
    #dp[0]=0
    for i in range(n):
        a=l[i]
        if a>m:
            break
        dp[a]=1

        for j in range(a+1,m+1):
            if dp[j-a]>0:
                if dp[j]==0:
                    dp[j]=dp[j-a]+1
                else:
                    dp[j]=min(dp[j],dp[j-a]+1)
    if dp[m]>0:
        return dp[m]
    else:
        return -1

print(fun(n, m, l))

编辑于 2021-06-08 14:52:45 回复(0)

Python

汤普森30

N, K = list(map(int, input().split()))
nums = list(map(int, input().split()))

dp = [float('inf')]*(K+1)
dp[0] = 0

for i in range(1, K+1):
    for j in range(N):
        if i < nums[j]:
            continue
        dp[i] = min(dp[i], dp[i-nums[j]]+1)
        
if dp[K] == float('inf'):
    print(-1)
else:
    print(dp[K])

发表于 2019-08-24 11:00:04 回复(0)