动态规划算法粗解及实例

2020-04-15 本文已影响0人爱吃西红柿嘛

微信公众号-可关注，如有需要会回关

复试在即，为反向刺激努力学习，日更不能断，没得写怎么办,强行写技术，技术不会怎么办，强行学习。其实是打游戏被队友坑的我不想再打了，你说说你打游戏不好好儿打上来就跟人家开喷，我辛辛苦苦努力耕耘把边路都打通了....哎，没办法游戏带不动或者比较坑只能码码字这样子，废话不说了，开始。

正文

0. 动态规划概念

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

如果你对对动态规划毫无了解，我们先来看看动态规划主要是解决哪一类的问题的。

典型应用

可以大概总结为：动态规划算法通常用于求解具有某种最优性质的问题。

0.1 要点：

把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解

在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。当然，各个阶段决策的选取不是任意确定的，它依赖于当前面临的状态，又影响以后的发展，当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线。这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题就称为多阶段决策问题。

多阶段决策问题

0.2 基本思想

在这类需要求解最优解的问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。

若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

分治法

0.3 理解

大家可能在公司里面都有一定的组织架构，可能有高级经理、经理、总监、组长然后才是小开发，今天我们通过这个例子，来讲讲什么问题适合使用动态规划。又到了一年一度的考核季，公司要挑选出三个最优秀的员工。一般高级经理会跟手下的经理说，你去把你们那边最优秀的3个人报给我，经理又跟总监说你把你们那边最优秀的人报给我，经理又跟组长说，你把你们组最优秀的三个人报给我，这个其实就动态规划的思想！

重叠子问题，不同的问题，可能都要求1个相同问题的解。假如A经理想知道他下面最优秀的人是谁，他必须知道X,Y,Z,O,P组最优秀的人是谁，甲总监想知道自己下面最优秀的人是谁，也要去知道X,Y,Z组里面最优秀的人是谁？这就有问题重叠了，两个人都需要了解X,Y,Z三个小组最优秀的人。
最优子结构，最优解肯定是有最优的子解转移推导而来，子解必定也是子问题的最优解。甲总监下面最优秀的3个人肯定是从X,Y,Z提交上来的3份名单中选择最优秀的三个人。例如Q哥是X组长下面的第5名，那么他肯定不可能是甲总监下面最优秀的三个。
无后效性，这个问题可能比较难理解，也就是求出来的子问题并不会因为后面求出来的改变。我们可以理解为，X组长挑选出三个人，即便到了高级经理选出大部门最优秀的三个人，对于X组来说，最优秀的还是这3个人，不会发生改变。

0.4 分类

动态规划一般可分为线性动规，区域动规，树形动规，背包动规四类。

线性动规：拦截导弹，合唱队形，挖地雷，建学校，剑客决斗等；
区域动规：石子合并，加分二叉树，统计单词个数，炮兵布阵等；
树形动规：贪吃的九头龙，二分查找树，聚会的欢乐，数字三角形等；
背包问题：01背包问题，完全背包问题，分组背包问题，二维背包，装箱问题，挤牛奶等；

应用实例：

最短路径问题
项目管理
网络流优化

1. 动态规划实例及代码分析

1.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元。

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

那么，现在我们怎样才能避免鼠目寸光呢？

如果直接暴力枚举凑出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来凑出15cost就是 $f(10)+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(1) +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)求出来不就好了？注意一下边界情况即可。代码如下：

我们以 $O(n)$ 的复杂度解决了这个问题。现在回过头来，我们看看它的原理：

$f(n)$ 只与 $f(n-1)$ , $f(n-5)$ ， $f(n-11)$ 的值相关。
我们只关心 $f(w)$ 的值，不关心是怎么凑出w的。

这两个事实，保证了我们做法的正确性。它比起贪心策略，会分别算出取1、5、11的代价，从而做出一个正确决策，这样就避免掉了“鼠目寸光”！

它与暴力的区别在哪里？我们的暴力枚举了“使用的硬币”，然而这属于冗余信息。我们要的是答案，根本不关心这个答案是怎么凑出来的。譬如，要求出f(15)，只需要知道f(14),f(10),f(4)的值。其他信息并不需要。我们舍弃了冗余信息。我们只记录了对解决问题有帮助的信息——f(n).

我们能这样干，取决于问题的性质：求出f(n)，只需要知道几个更小的f(c)。我们将求解f(c)称作求解f(n)的“子问题”。

这就是DP（动态规划，dynamic programming）.

将一个问题拆成几个子问题，分别求解这些子问题，即可推断出大问题的解。

1.2 几个简单的概念

【无后效性】　　
一旦f(n)确定，我们如何凑出f(n)”就再也用不着了。要求出f(15)，只需要知道f(14),f(10),f(4)的值，而f(14),f(10),f(4)是如何算出来的，对之后的问题没有影响。“未来与过去无关”，这就是无后效性　
（严格定义：如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响。）
【最优子结构】　　
回顾我们对f(n)的定义：我们记“凑出n所需的最少钞票数量”为f(n)。f(n)的定义就已经蕴含了“最优”。利用w=14,10,4的最优解，我们即可算出w=15的最优解。大问题的最优解可以由小问题的最优解推出，这个性质叫做“最优子结构性质”。

问：引入这两个概念之后，我们如何判断一个问题能否使用DP解决呢？　　
答： 能将大问题拆成几个小问题，且满足无后效性、最优子结构性质。

1.3 DP的典型应用：DAG最短路

问题很简单：给定一个城市的地图，所有的道路都是单行道，而且不会构成环。每条道路都有过路费，问您从S点到T点花费的最少费用。

一张地图。边上的数字表示过路费。

这个问题能用DP解决吗？我们先试着记从S到P的最少费用为f(P).想要到T，要么经过C，要么经过D。从而 $f(T)= min{f(C) + 20, f(D) + 10}$ .

好像看起来可以DP。现在我们检验刚刚那两个性质：

无后效性：对于点P，一旦f(P)确定，以后就只关心f(P)的值，不关心怎么去的。
最优子结构：对于P，我们当然只关心到P的最小费用，即f(P)。如果我们从S走到T是 $S→P→Q→T$ ,那肯定S走到Q的最优路径是 $S→P→Q$ 对一条最优的路径而言，从S走到沿途上所有的点（子问题）的最优路径，都是这条大路的一部分。这个问题的最优子结构性质是显然的。

既然这两个性质都满足，那么本题可以DP。式子明显为：
$f(P)= min{f(R) +WR→P .}$

其中R为有路通到P的所有的点， $WR→P$ 为R到P的过路费。

代码实现也很简单，拓扑排序即可。

1.4 对DP原理的一点讨论

【DP的核心思想】　　
DP为什么会快？　　
无论是DP还是暴力，我们的算法都是在可能解空间内，寻找最优解。　
来看钞票问题。暴力做法是枚举所有的可能解，这是最大的可能解空间。DP是枚举有希望成为答案的解。这个空间比暴力的小得多。　
也就是说：DP自带剪枝。　　
DP舍弃了一大堆不可能成为最优解的答案。譬如：　　
15 = 5+5+5 被考虑了。　　
15 = 5+5+1+1+1+1+1 从来没有考虑过，因为这不可能成为最优解。
从而我们可以得到DP的核心思想：尽量缩小可能解空间。
在暴力算法中，可能解空间往往是指数级的大小；如果我们采用DP，那么有可能把解空间的大小降到多项式级。
一般来说，解空间越小，寻找解就越快。这样就完成了优化。
【DP的操作过程】
　　一言以蔽之：大事化小，小事化了。
　　将一个大问题转化成几个小问题；
　　求解小问题；
　　推出大问题的解。

2. 例题及解释

最长上升子序列

最长上升子序列（LIS）问题：给定长度为n的序列a，从a中抽取出一个子序列，这个子序列需要单调递增。问最长的上升子序列（LIS）的长度。

e.g. $1,5,3,4,6,9,7,8$ 的LIS为 $1,3,4,6,7,8$ 长度为6。

如何设计状态（我是谁）？
　我们记 $f(x)$ 为以 $ax$ 结尾的LIS长度，那么答案就是 $max{f(x)}$
状态x从哪里推过来（我从哪里来）？
考虑比x小的每一个p：如果 $ax> ap$ , 那么 $f(x)$ 可以取 $f(p)+1$ .
解释：我们把 $ax$ 接在 $ap$ 的后面，肯定能构造一个以 $ax$ 结尾的上升子序列，长度比以 $ap$ 结尾的LIS大1.那么，我们可以写出状态转移方程了：

至此解决问题。两层for循环，复杂度 $O(n2)$