Kerberos认证原理 压制组装机 拓展培训公司 extjs enums timer Keys.js bootstrap管理模板 郑州小程序公司 list获取最后一个元素 android富文本框架 matlab向量的模 oracle查询数据库 webapp打包 python读取数据库 python语言编程 python正则匹配数字 java数据库 java如何配置环境变量 java中的集合 js选项卡 microkms 手机照片恢复免费软件 跳一跳脚本 英雄联盟体验服转换器 全英雄守城战 lol语音包 js文件上传 神魔辅助 一键root软件下载 炫舞爱的惊喜 暴力猴 ps怎么磨皮祛痘 软件编程软件 护魂者的命运 perl正则表达式 topaz滤镜 打印机暂停 pdf分割合并工具 打字机字体
当前位置: 首页 > 学习教程  > python

背包型动态规划——零钱兑换

2021/2/7 9:55:40 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。 你可以认为每种硬币的数量是无限的。 示例: 输入:coins [1, 2, 5], amount 1…

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额,返回 -1。

你可以认为每种硬币的数量是无限的。

示例:

输入:coins = [1, 2, 5], amount = 11
输出:3 
解释:11 = 5 + 5 + 1
示例 2:

提示:

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 10的四次方

1、题目分析

这个题目就是典型的背包问题6的应用。

2、代码实现

import numpy as np
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [10000 for i in range(amount+1)]
        dp[0]=0
        for i in range(amount+1):
            for j in coins:
                if i>=j and dp[i-j]!=10000:
                    dp[i]=min(dp[i],dp[i-j]+1)

        if dp[amount]==10000:
            return -1
        else:
            return dp[amount]        


本文链接: http://www.dtmao.cc/news_show_2000214.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?