【Leetcode刷题Python】518. 零钱兑换 II
2023-09-14 09:13:00 时间
1 题目
给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。
假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
示例 1:
输入:amount = 5, coins = [1, 2, 5]
输出:4
解释:有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
2 解析
状态:金额
转移:一个硬币,这个硬币的金额在coins[]数组中遍历
dp函数:输入金额,返回当前金额,在不同硬币下的组合数量
第一轮,我们计算以x1为基本数的组合数。
第二轮,我们计算x2为基本数的组合数。并将x2加到x1上,得到x1 + x2。
第三轮,我们计算x3为基本数的组合数。并将x2加到x1 + x2上,得到x1 + x2 + x2。
对amount为5而言
x1 有 {1, 1, 1, 1, 1}
x2 有 {1, 1, 1, 2}, {1, 2, 2}
x3 有 {1, 1, 3}, {2, 3}
最终返回x1 + x2 + x3。
由此可以得到动态规划的做法:
初始化 dp[0]=1;
遍历 coins,对于其中的每个元素 coin,进行如下操作:
遍历 i 从 coin 到 amount,将 dp[i−coin] 的值加到 dp[i]
最终得到 dp[amount] 的值即为答案。
上述做法不会重复计算不同的排列。因为外层循环是遍历数组
coins 的值,内层循环是遍历不同的金额之和,在计算 dp[i] 的值时,可以确保金额之和等于 i 的硬币面额的顺序,由于顺序确定,因此不会重复计算不同的排列
3 Python实现
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [0]*(amount+1)
dp[0] = 1
for coin in coins:
for i in range(coin,amount+1):
dp[i] += dp[i-coin]
return dp[amount]
相关文章
- python re.compile() 详解——Python正则表达式「建议收藏」
- 更新pycharm版本_pycharm怎么更改python环境
- python中关于命名的例子_Python 命名规范入门实例「建议收藏」
- 手机python 3.8解释器_Python 3.8 解释器安装教程
- python3 gil锁_python同步锁
- json转字符串 python_Python读取json
- Python标识符的命名规则,下列哪些是对的?_python标识符不能使用关键字
- python读取pkl_Python 读取文件
- Python绘制旭日图_python绘制散点图
- 使用Python爬取某网某电影视评论
- python绘制条形柱状图_Python柱状图
- 如何用Python内置模块构建简单的REST服务、RPC服务
- PyDbg安装(《Python 灰帽子》)
- Python中类的成员
- 【Android 逆向】frida 框架安装 ( 设置 Python 3.7 版本 | 安装 frida 12.7.5 版本 | 安装 frida-tools 5.1.0 版本 )
- python-Python与PostgreSQL数据库-使用Python执行PostgreSQL查询(二)
- Python枚举类定义和使用(详解版)
- python判断远程端口是否打开详解编程语言
- Python-面向对象编程(二)详解编程语言
- python的进程间的数据交互详解编程语言
- Linux与Python:开拓者的新时代(linux和python)
- 掌握Linux环境下的Python编程(linux执行python)
- python学习Linux、Python,体验自由的乐趣(lexlinux)
- Python中的函数:def
- Linux环境下Python开发的历程(linux与python)
- 利用Neo4j和Python进行无缝图形数据库支持(neo4j python)
- 在Python中简单调用MySQL(python调用mysql)
- 从 Python 连接到 MySQL:实现更多强大的数据库应用(python和mysql)
- 在Linux系统中使用Python编程语言(linux中python)
- python中使用enumerate函数遍历元素实例