题解 | 兑换零钱(一)

兑换零钱(一)

https://www.nowcoder.com/practice/3911a20b3f8743058214ceaa099eeb45

#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 最少货币数
# @param arr int整型一维数组 the array
# @param aim int整型 the target
# @return int整型
#
class Solution:
 
    def minMoney(self , arr: List[int], aim: int) -> int:
        # write code here
        if len(arr) == 0:

            return -1
        dp = [aim+1] * (aim+1)
        dp[0] =  0

        for i in range(len(arr)):
            for j in range(arr[i], aim+1):
                dp[j] = min(dp[j-arr[i]]+1, dp[j])
        if dp[aim] == aim+1:
            return -1
        return dp[aim]


全部评论

相关推荐

Lorn的意义:你这种岗位在中国现在要么牛马天天加班,要么关系户进去好吃好喝,8年时间,真的天翻地覆了,对于资本来说你就说一头体力更好的牛马,哎,退伍没有包分配你真的亏了。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务