什么是动态规划（Dynamic Programming）？动态规划的意义是什么？ - 知乎1
需积分: 0 89 浏览量
2022-08-03
21:06:44
上传
评论 9
收藏 2.4MB PDF 举报
12/23/2019 (3 封私信 / 4 条消息) 什么是动态规划（Dynamic Programming）？动态规划的意义是什么？ - 知乎
https://www.zhihu.com/question/23995189 1/61
138 个回答
默认排序
上海洛谷网络科技有限公司 讲师
专业 已有 5 人赠与了专业徽章
7,809 人赞同了该回答
0. intro
很有意思的问题。以往见过许多教材，对动态规划（DP）的引入属于“奉天承运，皇帝诏曰”式：
不给出一点引入，见面即拿出一大堆公式吓人；学生则死啃书本，然后突然顿悟。针对入门者的教材不
应该是这样的。恰好我给入门者讲过四次DP入门，迭代出了一套比较靠谱的教学方法，所以今天跑过来
献丑。
现在，我们试着自己来一步步“重新发明”DP。
1. 从一个生活问题谈起
先来看看生活中经常遇到的事吧——假设您是个土豪，身上带了足够的1、5、10、20、50、100
元面值的钞票。现在您的目标是凑出某个金额w，需要用到尽量少的钞票。
依据生活经验，我们显然可以采取这样的策略：能用100的就尽量用100的，否则尽量用50的……依
次类推。在这种策略下，666=6×100+1×50+1×10+1×5+1×1，共使用了10张钞票。
这种策略称为“贪心”：假设我们面对的局面是“需要凑出w”，贪心策略会尽快让w变得更小。
能让w少100就尽量让它少100，这样我们接下来面对的局面就是凑出w-100。长期的生活经验表明，贪
心策略是正确的。
但是，如果我们换一组钞票的面值，贪心策略就也许不成立了。如果一个奇葩国家的钞票面额分别
是1、5、11，那么我们在凑出15的时候，贪心策略会出错：
15=1×11+4×1 （贪心策略使用了5张钞票）
15=3×5 （正确的策略，只用3张钞票）
为什么会这样呢？贪心策略错在了哪里？
鼠目寸光。
刚刚已经说过，贪心策略的纲领是：“尽量使接下来面对的w更小”。这样，贪心策略在w=15的局
面时，会优先使用11来把w降到4；但是在这个问题中，凑出4的代价是很高的，必须使用4×1。如果使
用了5，w会降为10，虽然没有4那么小，但是凑出10只需要两张5元。
在这里我们发现，贪心是一种只考虑眼前情况的策略。
阮行止
剩余60页未读，继续阅读
评论0