python换零钱_Python3算法实例 1.2：动态规划之换零钱

作者：Cpp五条 | 2024-03-15 19:15:02

踩

100元能分5元、10元,20元各一张有多少种方法python代码

b416db467400?utm_source=oschina-app

money.jpg

问题(基础版)：

把100元兑换成1元，2元，5元，10元，20元，50元的零钱，共有多少种不同换法。

动态规划思想解析：

拆解子问题

下面以5元换成1,2,3元的零钱为例。T[(change),target]表示用零钱序列change组成target的所有方法。见下图：

b416db467400?utm_source=oschina-app

example.png

其中：

T1[(1,2)，5-0*3]可看作只用1和2元、不用3元组成5元的方法数；

T2[(1,2)，5-1*3]可看作用1和2元、并且只用1个3元组成5元的方法数；

T6[(1)，3]可看作用1元，只用1个2元、并且不用3元组成5元的方法数；

T9[(1)，0]可看作用1元，只用1个2元、只用1个3元组成5元的方法数。

状态转移表达式：

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Cpp五条/article/detail/243878

python换零钱_Python3算法实例 1.2：动态规划 之 换零钱