动态规划

动态规划(dynamic programming)

动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。

20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。

1957年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作。

动态规划最核心的思想，就在于拆分子问题，记住过往，减少重复计算。

什么是动态规划（Dynamic Programming）？动态规划的意义是什么？ - 阮行止的回答 - 知乎

先来看看生活中经常遇到的事吧——假设您是个土豪，身上带了足够的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元。

在这里我们发现，贪心是一种只考虑眼前情况的策略。

那么，现在我们怎样才能避免鼠目寸光呢？如果直接暴力枚举凑出w的方案，明显复杂度过高。太多种方法可以凑出w了，枚举它们的时间是不可承受的。我们现在来尝试找一下性质。

重新分析刚刚的例子。w=15时，我们如果取11，接下来就面对w=4的情况；如果取5，则接下来面对w=10的情况。我们发现这些问题都有相同的形式：“给定w，凑出w所用的最少钞票是多少张？”接下来，我们用f(n)来表示“凑出n所需的最少钞票数量”。

那么，如果我们取了11，最后的代价（用掉的钞票总数）是多少呢？

cost = f(4)+1 = 4+1 = 5，它的意义是：利用11来凑出15，付出的代价等于f(4)加上自己这一张钞票。现在我们暂时不管f(4)怎么求出来。　　依次类推，马上可以知道：如果我们用5来凑出15，cost就是f(10)+1=2+1 = 2 + 1  = 3

那么，现在w=15的时候，我们该取那种钞票呢？当然是各种方案中，cost值最低的那一个！　　

- 取11：cost=f(4)+1=4+1=5　　

- 取5：  cost=f(10)+1=2+1=3　　

- 取1：  cost=f(14)+1=4+1=5　　

显而易见，cost值最低的是取5的方案。我们通过上面三个式子，做出了正确的决策！

这给了我们一个至关重要的启示—— f(n)只与 f(n−1),f(n−5),f(n−11)相关；更确切地说：

f(n)=min{f(n−1),f(n−5),f(n−11)}+1

这个式子是非常激动人心的。我们要求出f(n)，只需要求出几个更小的f值；既然如此，我们从小到大把所有的f(i)求出来不就好了？注意一下边界情况即可。

动态规划理解起来还是比较困难，什么重叠子问题、动态转移方程，优化点等等等等，好好看着其他人的分享，每个理解了一部分，然后疯狂刷他几十道。算是基本可以佛挡杀佛了。

https://www.bilibili.com/video/BV1AB4y1w7eT

动态规划题目

不同路径

https://leetcode.cn/problems/unique-paths/description/

https://leetcode.cn/problems/unique-paths-ii/description/

打家劫舍I

https://leetcode.cn/problems/house-robber/

参考文章：

动态规划一篇就够了 全网第二详细, 逐步理解, 万字总结 https://cloud.tencent.com/developer/article/1692068

五大基本算法之动态规划算法 DP https://houbb.github.io/2020/01/23/data-struct-learn-07-base-dp

转载本站文章《动态规划》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/leetcode/9100.html