算法学习——动态规划（Python代码）_动态规划代码

一、问题的提出

我们来看这样一个问题

• 你有三种硬币，分别面值2元、5元和7元，每种硬币都有足够多
• 买一本书需要27元
• 如何用最少的硬币组合起来正好付清，不需要对方找钱

我们直觉会怎么想？

你有三种硬币，分别面值2元、5元和7元，每种硬币都有足够多，买一本书需要27元，如何用最少的硬币组合起来正好付清，不需要对方找钱

• 最少的硬币组合➡尽量用面值大的硬币

√ 7+7+7+7=28

√ 7+7+7=21

√ 21+5=26

√ 这样显然拼不出来

• 改一下思路➡先用面值大的硬币,最后如果可以用一种硬币付清就行

√ 7+7+7=21

√ 21+2+2+2=27

√ 这次应该对了吧，其实正确答案是：7+5+5+5+5=27，5枚

所以我们需要更加科学的方法来计算这个问题

二、基本原理

1、基本概念

动态规划是运筹学的一个分支，通常用来解决多阶段决策过程最优化问题。动态规划的基本想法就是将原问题转换为一系列相互联系的子问题，然后通过逐层地推来求得最后的解。目前，动态规划常常出现在各类计算机算法竞赛或者程序员笔试面试中，在数学建模中出现的相对较少，但这个算法的思想在生活中非常实用，会对我们解决实际问题的思维方式有一定启发。

添加图片注释，不超过 140 字（可选）

2、基本步骤

一、 确定状态：解动态规划的时候需要开一个数组，数组的每个元素需要明确代表什么，类似于确定数学题中X、Y的含义

√ 最后一步 √ 子问题

二、转移方程：把状态表达成方程

三、初始条件和边界情况

四、 计算顺序

三、典型例题

1、问题

你有三种硬币，分别面值2元、5元和7元，每种硬币都有足够多，买一本书需要27元，如何用最少的硬币组合起来正好付清，不需要对方找钱

一、确定状态

最后一步：

• 虽然我们不知道最优策略是什么，但是最优策略肯定是有k枚硬币，

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