动态规划算法

2020-10-24 本文已影响0人 ITsCLG

动态规划（Dynamic Programming，DP）是算法设计思想中最难也是最有趣的部分。掌握动态规划算法，对于大厂面试是必不可少的。有接触过DP的小伙伴也许会联想到许许多多的名词，如什么状态转移方程什么的；要不就想到教材书上严谨而又晦涩难懂的对于动态规划的介绍；也有人想到高中的通项公式或数列题等等，但是左看右看都看不出动态体现在哪？哈哈，按照MIT编程导论老师的说法，就是创建人为了不让军方知道他在做什么而故意胡诌的一个名词。后续了解有关算法的实现，我们或许可以用分步规划法、分步存储法、递推存储法、数列递推法、状态转移法等等来重命名它。

其实，小编本人掌握动态规划的过程，也是一波三折，经历九九八十一难。接下来，小编借助几个例子，谈谈自己对DP算法的一点理解。

一、斐波那契数列看DP思想

斐波那契数列：0，1，1，2，3，5，8，13，21，34，55，89，144，233 ……

它遵循这样的规律：当前值为前两个值的和

那么第n个值为多少？

这其实是一个数列，学过数列的小伙伴应该知道，如果数列{an}的第n项与它前一项或几项的关系可以用一个式子来表示，那么这个公式叫做这个数列的递推公式。那么斐波那契数列的递推公式就是f(n)=f(n-1)+f(n-2)。我们来分析下问题的解决方法。

（一）暴力递归

我们常见的是使用暴力递归的算法来解决这个问题，代码如下：

暴力递归

如上所示，代码简单易懂，然而代码却极其低效。这种使用递归的方式一方面不仅造成栈空间的极大浪费，另一方面该算法的时间复杂度为 $O(2^n)$ ，指数级别。我们可以看下f(20)的求解过程，这其实就是一棵树。可以看到 f(18) 被计算了两次，而且你可以看到，以 f(18) 为根的这个递归树体量巨大，多算一遍，会耗费巨大的时间。更何况，还不止 f(18) 这一个节点被重复计算，随着递归的深入，计算任务不断翻倍，所以这个算法及其低效。

递归树

这就是动态规划可解决的问题经常出现的情况：重叠子问题。下面，我们想办法解决这个问题。

（二）自顶向下的记忆化搜索递归

即然耗时的原因是重复计算，那么我们可以造一个数组，每次算出某个子问题的答案后别急着返回，先记到数组里再返回；每次遇到一个子问题先去数组里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了。

代码如下：

自顶向下的记忆化搜索递归

"记忆化搜索"或者我们称"重叠子问题"的加缓存优化的实现，我们的思考路径是"自顶向下"。即为了解决数据规模大的问题，我们“假设”已经解决了数据规模较小的子问题。我们没有从最基本的问题开始求解，对于f(n)=f(n-1)+f(n-2)，我们假装f(n-1)和f(n-2)是已知的。现在，画出图，你就知道数组到底做了什么。

重叠子问题

实际上，带数组的递归算法，把一棵存在巨量冗余的递归树通过裁剪，改造成了一幅不存在冗余的递归图，极大减少了子问题（即递归图中节点）的个数。

剪枝

经过分析，本算法的时间复杂度是 $O(n)$ 。

至此，带数组的递归解法的效率已经和迭代的动态规划解法一样了。实际上，这种解法和迭代的动态规划已经差不多了，只不过这种方法叫做自顶向下，动态规划叫做自底向上。关于自顶向下和自底向上的意思这里就不做描述，不懂的可以找度娘。

（三）自底向上的动态规划思想

有了上一步的启发，我们可以把这个数组独立出来成为一张表。

① 斐波那契数列有这样的关系：f(n)=f(n-1)+f(n-2)

② 我们使用一个数组result[ ]，来缓存这些重复计算的值。因此有：

result[i]= result[i-1]+ result[i-2]

采用这样的方法我们就可以对缓存的数据进行复用。

③ 按顺序从小往大算。使用for循环实现了从0到n的顺序求解，问题从小规模往大规模求解的顺序走。

DP思想

代码如下：

自底向上的DP解决算法

同样的，时间复杂度降为O(n)。

其实，上述斐波那契数列就是使用了DP思想来解决这个问题。

用动态规划思想来解决问题，归根到底就是三个步骤：

① 建立递推公式

② 根据递推公式建立一个数组，用来缓存并复用以往结果

③ 运用循环控制结构，按顺序从小往大算，得到最终结果

当然，这里的递推公式，在DP里称呼为状态转移方程，数组又称呼为DP表。往下看，小编稍后还会进行解释。

二、凑硬币问题探DP性质

当然，DP思想主要使用在求解最值问题这一类问题上，上述斐波那契数列只不过是用来描述下DP思想解决问题的基本的步骤及其使用价值。

凑硬币问题：现在有面值为1，5，11的硬币若干。现在您的目标是凑出某个金额w，需要用到尽量少的硬币。

依据生活经验，我们每次都是先挑面值大的硬币，按这样的方法来凑够金额。这就是所谓的“贪心策略”。我们面对的局面是“需要凑出w”，贪心策略会尽快让w变得更小。能让w少11就尽量让它少11，这样我们接下来面对的局面就是凑出w-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，最后的代价（凑出来的总硬币个数）是多少呢？

明显f(15)=f(15-11)+1=f(4)+1=4+1=5，它的意义是：利用11来凑出15，付出的代价等于f(4)加上自己这一枚硬币。现在我们暂时不管f(4)怎么求出来。

依次类推，马上可以知道：如果我们用5来凑出15，cost就是f(15)=f(15-5)+1=f(10)+1=2+1=3；

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

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

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

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

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

这给了我们一个至关重要的启示：f(n)只与f(n-11)，f(n-5)，f(n-1)有关，也就是：

$f(n)=min\left\{ f(n-11), f(n-5), f(n-1) \right\} +1$

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

代码如下：

凑硬币问题

可以发现，求出f(n)，只需要知道几个更小的f(c)。我们将求解f(c)称作求解f(n)的“子问题”。将一个问题拆成几个子问题，分别求解这些子问题，即可推断出大问题的解。这就是DP（动态规划，dynamic programming）

看看上述的分析，我们也可以来引入两个新的概念：

① 无后效性

一旦f(n)确定，“我们如何凑出f(n)”就再也用不着了。观察递推公式可知，f(n)只与f(n-11)，f(n-5)，f(n-1)有关。我们只关心f(w)的值，不关心是怎么凑出w的。我们将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思想解决，一方面看能否将大问题拆成几个小问题，且满足无后效性、最优子结构性质。

三、DAG最短路径观多阶段决策

或许很多小伙伴对状态转移方程感到陌生，啥是状态。当然，这方面的内容就跟数学有更大的联系了。

最短路径问题：在下面的线路网络图中，从A至E有一批货物需要调运。图上所标数字为各节点之间的运输距离，为使总运费最少，必须找出一条由A至E总里程最短的路线。

线路网络图

① 阶段：阶段(step)是对整个过程的自然划分。通常根据时间顺序或空间特征来划分阶段，以便按阶段的次序解优化问题。阶段变量一般用k=1,2,..,n表示。我们可以把上图分为5个阶段，由A出发为k=1，由 $B_{i}$ (i=1,2,3)出发为k=2，依此下去从 $D_{i}$ (i=1,2,3)出发为k=4，由E出发k=5，这几个阶段相互联系。

② 状态：通常一个阶段有多个状态，上图中第一阶段的状态就是A，第二阶段的状态就是{ $B_{1}$ , $B_{2}$ }，即第k阶段所有出发点的集合。描述过程状态的变量称为状态变量，可用一个数，一组数或一个向量来描述，常用 $S_{k}$ 表示第 k 阶段的状态变量。如 $S_{3}$ = { $C_{1}$ , $C_{2}$ , $C_{3}$ }。

③ 决策：决策表示当过程处于某一阶段某一状态时，可以做出的决定，从而确定下一阶段的状态，这个决定就叫做决策。描述决策的变量，称为决策变量。可以是一个数，一组数，也可以是一个向量。分析上图，我们可以发现，在每个阶段都需要作出决策，即在A点需决策下一步到 $B_{1}$ 还是到 $B_{2}$ 或 $B_{3}$ ；同样，若到达第二阶段某个状态，比如 $B_{1}$ ，需决定走向 $C_{1}$ 还是 $C_{2}$ ；依次类推，可以看出各个阶段的决策不同，由A至E的路线就不同，当从某个阶段的某个状态出发作出一个决策，则这个决策不仅影响到下一个阶段的距离，而且直接影响后面各阶段的行进线路。所以这类问题要求在各个阶段选择一个恰当的决策，使这些决策序列所决定的一条路线对应的总路程最短。

我们使用 $U_{k}$ 来表示决策变量，可以发现决策变量 $U_{k}$ 还是状态变量 $S_{k}$ 的函数。因此，又可将第k阶段 $S_{k}$ 状态下的决策变量记为 $U_k (S_k)$ ，也就是处于不同的状态时所能做的决策与当前状态有关。

④ 状态转移方程：状态转移方程是确定过程由一个状态到另一个状态的演变过程。由前面的讨论我们知道，如果给定第 k 个阶段的状态变量 $S_k$ 的取值，那么该阶段的决策变量 $U_k (S_k)$ 一经确定，第 k+1 阶段的状态变量 $U_{k+1} (S_{k+1})$ 的取值也就决定了。即 $S_{k+1}$ 的值随 $S_k$ 和 $U_k$ 的值变化而变化，这种对应关系，记为 $S_{k+1}$ = $T(S_k, U_k)$ ，称之为状态转移方程。T为状态转移函数，在上例中，状态转移方程就是： $S_{k+1}$ = $U_k(S_k)$ 。

⑤ 策略：在一个多阶段决策过程中，如果各个阶段的决策变量 $U_k(S_k)$ （k=1，2，…，n）都已确定，则整个过程也就完全确定。称 $\left\{ U_k (S_k), U_{k+1}(S_{k+1}), … , U_{k+n}(S_{k+n})\right\}$ 决策序列为该过程的一个策略，从阶段k到阶段n的决策序列称为子策略，表示成。如例1中，选取一路线 $A->B_1->C_2->D_2->E$ 就是一个策略，也就是：

$\left\{ U_1(A)=B_1, U_2(B_1)=C_2, U_3(C_2)=D2, U_4(D_2)=E \right\}$

由于每一阶段都有若干个可能的状态和多种不同的决策，因而一个多阶段决策的实际问题存在许多策略可供选择，称其中能够满足预期目标的策略为最优策略。上图中，我们通过此方法找到的最优的策略就是最短路径。

了解有关的概念后，怎么来找到这条最短路径呢？

容易看出，在最短路线问题中，找到的最短路径是 $A->B_1->C_2->D_2->E$ 。那么当然有 $C_2->D_2->E$ 也是从C2到E的最短路线。即如果由起点A经过P点和H点而到达终点E是一条最短路线，则由P出发经过H而到达E点的这条子路线，也必定是P点到达E点的最短路线。根据最短路线问题的这一特性，寻找最短路线问题的方法就是：从最后一段开始，用由后向前逐步递推的方法，求出各点到E点的最短路线，再求出A点到E点的最短路线。所以，动态规划的方法就是从终点逐段向起点方向寻找最短路线的一种方法，如下图所示：

DP思想

下面按照动态规划的方法，从最后一段开始计算，由后向前逐步推移至A点。（直接附书上方法了，了解思想后这个比较容易）。

我们使用 $F_k(S_k)$ 表示从第k阶段的状态开始到第n阶段的终止状态的过程，采取最优策略所得到的最优值。

当k=4时，从 $D_1$ 到E只有一条路线， $F_4(D_1)$ =7， $F_4(D_2)$ =8， $F_4(D_3)$ =6；

当k=3时，出发点有 $C_1$ ， $C_2$ ， $C_3$ 三个；

若从 $C_1$ 出发，有两个选择：①至 $D_1$ ；②至 $D_2$ ，所以 $F_3(C_1)$ = $min \left\{ distance(C_1,D_1)+F_4(D_1)，distance(C_1,D_2)+ F_4(D_2) \right\} =\left\{ 4+7，2+8\right\} =10$

其相应的决策为： $U_3 (C_1)=D_2$ ；

若从 $C_2$ 出发，有两个选择：①至 $D_2$ ；②至 $D_3$ ，所以 $F_3(C_2)=min\left\{ distance(C2,D2)+F4(D2)，distance(C2,D3)+ F4(D3)\right\} =\left\{ 5+8，7+6 \right\} =13$

其相应的决策为： $U_3 (C_2)=D_2$ ；

若从 $C_3$ 出发，有两个选择：①至 $D_2$ ；②至 $D_3$ ，所以 $F_3(C_3)=min\left\{distance(C3,D2)+F4(D2)，distance(C3,D3)+ F4(D3) \right\} =\left\{ 10+8，9+6\right\} =15$

其相应的决策为： $U_3 (C_3)=D_3$ ；

当k=2时，出发点有 $B_1$ $B_2$ ， $B_3$ 三个；

若从 $B_1$ 出发，有两个选择：①至 $C_1$ ；②至 $C_2$ ，所以 $F_2(B_1)=min\left\{ distance(B1,C1)+F3(C1)，distance(B1,C2)+ F3(C2) \right\} =\left\{ 6+10，4+13 \right\} =16$

其相应的决策为： $U_2 (B_1)=C_1$ ；

若从 $B_2$ 出发，有两个选择：①至 $C_1$ ；②至 $C_3$ ，所以 $F_2(B_2)=min\left\{ distance(B2,C1)+F3(C1)，distance(B2,C3)+ F3(C3)\right\} =\left\{ 3+10，8+15 \right\} =13$

其相应的决策为： $U_2 (B_2)=C_1$ ；

若从 $B_3$ 出发，有两个选择：①至 $C_2$ ；②至 $C_3$ ，所以 $F_2(B_3)=min\left\{ distance(B3,C2)+F3(C2)，distance(B3,C3)+ F3(C3) \right\} =\left\{ 8+13，4+15 \right\} =19$

其相应的决策为： $U_2 (B_3)=C_3$ ；

当k=1时，出发点有A一个；

所以 $F_1(A)=min\left\{ distance(A,B1)+ F2(B1)，distance(A,B2)+ F2(B2)，distance(A,B3)+ F2(B3) \right\}=\left\{ 4+16，5+13，3+19\right\} =18$

可以发现，在查找最短路径这类问题中，每个阶段的最优状态都可以从之前某个阶段的某个或某些状态直接得到，这就是所谓的“最优子结构”。

我们还可以发现，上述求解最短路径的过程中，某个阶段的状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。这就是“无后效性”。

按照计算顺序的反方向反推可以很容易得到最短路径为： $A->B_2->C_1->D_2->E$

由上我们可以得到k阶段与k+1阶段的递推关系：

$F_k(S_k)=min\left\{ distance(S_k, U_k (S_k))+ F_{k+1}(U_k (S_k)) \right\} k=4，3，2，1$

$F_5(S_5)=0$ 【或者写成 $F_4(S_4)= distance(S_4,E)$ 】。这个就是所谓的边界条件

当然，求最大值也是相同的思想来操作。

由此可见，动态规划是一种自底向上求解问题的思想。

这里呢，主要是讲了阶段，状态以及状态转移方程等等，我们接着往下看。

四、最长上升子序列窥DP解题思路

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

例子： a[7] = {1,6,4,2,3,9,8}，找到的最长的上升子序列（LIS）为{1,2,3,9}或者{1,2,3,8}，长度为4。

思想：这里用到的是自底向上的寻找最优子结构的的思想。粗俗来说：如果你想要得到七个数里面的最长子序列，你可以先找前6个数里面的最长子序列，同理，你又必须得找前5个数里面的最长子序列，直到子序列为1。

我们使用DP思想来解决这道问题，关键的是要设定好状态，找到状态转移方程，找到初值和边界条件，最后才能找到所需的答案。

我们来分析下：

数组d[i]:用数组d 来存储前第i个数的最长子序列，i表示的就前几个数。

毫无疑问有：

{1}：d[1]=1 : 表示第一个数他的最长子序列是1，最长上升子序列为{1}

{1,6}：d[2]=d[1]+1=2 : 表示前两个数中，最长上升子序列长度为2，最长上升子序列为{1,6}

{1,6,4}：d[3]=d[1]+1=2 : 因为4 < 6 所以不能用d[2]+1,但 1<4 所以是d[1]+1，最长上升子序列为 {1,6}和{1,4}

{1,6,4,2} ：d[4]=d[1]+1=2 ：4和6 都大于2 所以不能用d[2]，d[3]，最长上升子序列为{1,6}，{1,4}和{1,2}

{1,6,4,2,3} ：d[5]=d[4]+1=3 ：3 >2 ，所以d[4]+1=2+1=3，最长上升子序列为{1,2,3}

{1,6,4,2,3,9} ：d[6]=d[5]+1= 4 ：最长上升子序列是{1,2,3,9}

{1,6,4,2,3,9,8}：d[7]=4 ：最长上升子序列是{1,2,3,9} 或者{1,2,3,8}

通过分析，我们得到

状态：d[i]指在1~i这i个数中，必须包含a[i]这个数的最长上升子序列。

状态转移方程：if(a[j] < a[i]) d[i] = max(d[i], d[j] + 1)（1 <= j <= i - 1）

初值：d[i] = 1（一个数本身就是一个递增序列）

答案：max{d[i]}

接下来，我们就可以来编写代码了，如下所示：

最长的上升子序列（LIS）长度

可以看到程序有两个for循环，时间复杂度为 $O(n^2 )$ 。当然我们还可以采取一些优化手段，把时间复杂度降低到 $O(n\log_ n )$ ，这里小编不做解释。

五、DP解题的一般思路

通过上述几个最简单的例子，我们可以了解到有关的DP思想。动态规划所处理的问题是一个多阶段决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的模式，一般要经历以下几个步骤：

（1）划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。

（2）确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。

（3）确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。

（4）寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。

一般，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件）

六、算法实现的一般步骤

1、创建一个一维数组或者二维数组，保存每一个子问题的结果，具体创建一维数组还是二维数组看题目而定，基本上如果题目中给出的是一个一维数组进行操作，就可以只创建一个一维数组，如果题目中给出了两个一维数组进行操作或者两种不同类型的变量值，比如背包问题中的不同物体的体积与总体积，找零钱问题中的不同面值零钱与总钱数，这样就需要创建一个二维数组。

注：需要创建二维数组的解法，都可以创建一个一维数组运用滚动数组的方式来解决，即一位数组中的值不停的变化，后面会详细徐叙述

2、设置数组边界值，一维数组就是设置第一个数字，二维数组就是设置第一行跟第一列的值，特别的滚动一维数组是要设置整个数组的值，然后根据后面不同的数据加进来变幻成不同的值。

3、找出状态转换方程，也就是说找到每个状态跟他上一个状态的关系，根据状态转化方程写出代码。

4、返回需要的值，一般是数组的最后一个或者二维数组的最右下角。

代码基本框架：

DP思想解题基本框架

DP是一种思想，一种“大事化小，小事化了”的思想。带着这种思想，DP将会成为我们解决问题的利器。

上述是小编看了挺多资料自己总结的一点经验，由于能力不足所以有些理解的可能不是特别正确，也请指正，谢谢！

动态规划算法

猜你喜欢

热点阅读