蓝桥杯算法入家世17讲：DP基础+背包
动态规划（Dynamic Programming，DP）是Richard Bellman于1950年代发明的应用于多阶段决策的数学方法。和贪心、分治一样，动态规划是一种解题的思路。动态规划是一种需要学习才气得到的头脑方法。像贪心、分治如许的方法，在生活中，或在其他学科中有很多类似的例子，很容易联想和明确。但动态规划不是，它是一种生活中没有的抽象计算方法，没有学过的人很难自发产生这种思路。
动态规划是地地道道的“计算头脑”，非常适适用计算机实现，可以说是独属于计算机学科的计算理论。用下面的例子证明这一点。
李开复在1980年代发展了语音辨认技术，是当时世界顶尖的科技。关于语音辨认中的动态规划，他讲过一个故事：“还记得1988年贝尔实验室副总裁亲自来访问我的学校，目的就是为了想相识为什么他们的语音辨认体系比我开发的慢几十倍，而且，在扩大至大词汇体系后，速度差异更有几百倍之多。他们虽然买了几台超级计算机，勉强让体系跑了起来，但这么贵的计算资源让他们的产物部门很反感，因为“昂贵”的技术是没有应用前景的。在与他们探讨的过程中，我惊奇地发现一个O(n×m)的动态规划居然被他们做成了O(n×n×m)。更惊奇的是，他们还为此发表了不少文章，甚至为自己的算法起了一个很特别的名字，并将算法提名到一个科学集会里，希望能得到大奖。贝尔实验室的研究员固然绝顶聪明，但他们全都是学数学、物理或电机出身，从未学过计算机科学或算法，才犯了这么基本的错误。我想那些人以后再也不会嘲笑学计算机科学的人了吧！”
这个例子清楚地阐明，动态规划这种基础的计算理论，其他工程学科的人假如没有学过，很难想到有这种方法。贝尔实验室的工程师们无疑是顶级的，但是仍旧“犯了这么基本的错误”。
动态规划是Richard Bellman于1950年代发明的应用于多阶段决策的数学方法。三十年后的1980年代，贝尔实验室的人仍旧不知道这个理论，可想而知，那时计算机还只是被当成一个计算工具，计算理论远未普及。
DP是算法竞赛中最常见的考点之一，蓝桥杯大赛每次必有DP题目，少则一题，多则数题。
可以说，会做DP题目，就有很大概率得到蓝桥杯省赛一等奖。
不过，DP专题的内容非常多，有线性DP、区间DP、状态压缩DP、树形DP、DP优化等等。蓝桥杯的DP大多是线性DP，比年来也出现了一些非线性DP的内容。在知识点上，线性DP比其他DP内容简单；在头脑上，线性DP也可以出很难的题目。
初学者从线性DP开始学习，创建干系的计算头脑。
动态规划概念
有一些问题有两个特征：重叠子问题、最优子布局。用DP可以高服从地处理具有这两个特征的问题。
（1）重叠子问题
首先，子问题是原大问题的小版本，计算步骤完全一样；其次，计算大问题的时间，需要多次重复计算小问题。这就是“重叠子问题”。
一个子问题的多次计算，泯灭了大量时间。用DP处理重叠子问题，每个子问题只需要计算一次，从而制止了重复计算，这就是DP服从高的原因。具体的做法是：首先分析得到最优子布局，然后用递推大概带影象化搜索的递归举行编程，从而实现了高效的计算。
（2）最优子布局
最优子布局的意思是：首先，大问题的最优解包含小问题的最优解；其次，可以通过小问题的最优解推导出大问题的最优解。
用斐波那契数为例阐明DP的概念。
斐波那契数列是一个递推数列，第n个数便是第n-1个和第n-2个相加，前几个斐波那契数是1、1、2、3、5、8。斐波那契数的递推公式是：
fib(n) = fib(n-1) + fib(n-2)
斐波那契数列又称为兔子数列。设一对兔子每月能生一对小兔子，小兔子在出生的第一个月没有生殖本事，第二个月便能生育，且所有兔子都不会殒命。从第一对刚出生的兔子开始，问12个月以后会有多少对兔子？读者可以画个图模拟兔子的增长过程，看兔子的数量变化是不是符合斐波那契数列。
https://i-blog.csdnimg.cn/img_convert/24f689a8b3f0635b7930b61f399a9802.png
斐波那契数列也经常用“走楼梯问题”来举例。一次可以走一个台阶大概两个台阶，问走到第n个台阶时，一共有多少种走法？要走到第n级台阶，分成两种情况，一种是从n-1
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]