数据结构与算法设计分析——动态规划

一、动态规划的定义

动态规划的基本思想是将问题分成若干个子问题，先求解子问题，然后从子问题的解进而得到原问题的解。

二、动态规划的基本要素和主要步骤

动态规划算法的两个基本要素是最优子结构和重叠子问题，其主要步骤如下：
①问题需要具有最优子结构性质；
②构造最优值的递归表达式；
③最优值的算法描述；
④构造最优解。

（一）最优子结构

问题可分为若干个子问题，最优子结构指的是问题的最优解可以由其子问题的最优解求解出来，它的也是依据将复杂问题分解成简单子问题的方法。总的来说，某一问题可用动态规划算法求解的显著特征是该问题具有最优子结构性质。

（二）重叠子问题

当划分的子问题中有些子问题重复出现时，这些问题是会被重复计算和求解的，从而会导致算法效率低且造成空间开销，而动态规划的优势在求解划分的重叠子问题的时候，将第一次求解的解通过数组或表存储起来，从而可以避免重复计算后面相同的子问题。

三、贪心法、分治法和动态规划的对比

（一）贪心法

每一步都选择当前最优解，而不考虑该决策对整体的影响。贪心算法通常适用于简单、容易分解的问题，即具有贪心选择性质和最优子结构两个重要的性质的问题求解。贪心法总是做出最好的选择，可以快速地得到近似上的最优解的情况（局部最优选择），时间复杂度较低，但其缺点是不能保证得到全局上的最优解。

（二）分治法

可分为分解、治理两大步骤，其通常适用于优化问题，采用递归的思想，每次将问题分成两个或更多的小问题，由于各个子问题是相互独立的，所以通过递归最终合并可以很容易得到原问题的解，但若各个子问题不是相互独立的时，则会造成重复，从而会有很高的时间复杂度。

（三）动态规划

与分治法不同的是，动态规划通常解决的是重叠子问题性质和最优子结构性质的问题，其中解决子问题只需一次，解决后会将其解保存并重复使用，避免重复计算。动态规划通常采用自底向上的方式，通过先解决子问题，再解决大问题的方式进行求解。动态规划适合用于优化问题，并且能够保证得到全局最优解。但对比贪心法、分治法算法，由于需要存储各种状态，所以其需要的空间更大。

三种算法的对比如下表：

名称	贪心法	分治法	动态规划
适用性	一般问题	优化问题	优化问题
求解	线性求解	递归求解	递归和迭代求解
求解顺序	先选择后解决子问题	先选择后解决子问题	先解决子问题后选择
特征	由顶向下	由顶向下	由顶向下、由底向上
最优子结构	满足	不满足	满足
子问题规模	仅一个子问题	所有子问题	所有子问题
子问题独立性	仅一个子问题	每个子问题独立	每个子问题重叠不独立
子问题最优解	部分最优解	全部最优解	部分最优解

四、动态规划的递归和迭代法求解

（一）由顶向下的递归法

由顶向下的递归法也被称为带记忆的由顶向下法，可概括为递归+可记忆，是一种自上而下的分治思想，一开始将问题分成子问题，通过递归先解决子问题，这里的可记忆指的是保存每个子问题的解，这些解被保存到一个数组或表格中，其目的是为了避免重复计算，节省时间。该方法通常由递归函数实现，同时，结合记忆化可以消除重复计算，从而大幅度提升计算效率，缩短时间。

（二）由底向上的迭代法

由底向上的迭代方法可概括为迭代+动态规划，是一种自下而上的构建思想。通过将问题分成相互独立、可简单直接求解的子问题，并将子问题的解按由小到大的顺序保存下来，逐步构建出问题的最优解，即当求解某个子问题时，其所依赖的更小的子问题已经是求解了的，从而每个子问题只需求解一次即可。该方法通常由循环语句实现，可以避免采用递归函数时所带来的额外开销。

以上两种方法具有相同的渐进运行时间，仅有的差异是在某些特殊情况下，由顶向下方法并未真正递归地考察所有可能的子问题。由于没有频繁的递归函数调用的开销，由底向上方法的时间复杂性函数通常具有更小的系数。

五、动态规划的应用

（一）斐波那契数列

由斐波那契数列（Fibonacci），可得
递归关系式：F(n) = F(n-1) + F(n-2) ，
其中F(0)=0，F(1) = F(2) = 1。

f(n)的求解可以类比一棵二叉树，以F(5)为例，根据递归关系式可画出二叉树，如下图：

1、若采用不带记忆的由顶向下的递归法时，其中有重复的子问题，会造成重复计算，从而加大开销，且当计算的n值越来越大时，空间开销会更大。
所以，采用带记忆的由顶向下的递归法，通过建立一个一维数组来保存每个子问题的解，当计算时，只需从数组中取出相应的值即可，从而可以避免重复计算【避免子问题重叠】。这种方法只需求需要的相应值即可，该树中，有重复的子问题如下：

创建一个数组，首先将F(0)、F(1)和F(2)的解存在数组中，如下：

	F(0)	F(1)	F(2)
数组	0	1	1

求解F(3)时，根据递归关系式，F(n) = F(n-1) + F(n-2) ，即F(3) = F(2) + F(1) =1+1=2，直接取数组中F(2)和F(1)的值代入计算即可，然后将F(3)存放在数组中，如下：

	F(0)	F(1)	F(2)	F(3)
数组	0	1	1	2

求解F(4)时，根据递归关系式，F(n) = F(n-1) + F(n-2) ，即F(4) = F(3) + F(2) =2+1=3，直接取数组中F(3)和F(2)的值代入计算即可，然后将F(4)存放在数组中，如下：

	F(0)	F(1)	F(2)	F(3)	F(4)
数组	0	1	1	2	3

……依次最终求得F(5)=F(4) + F(3)=3+2=5：

	F(0)	F(1)	F(2)	F(3)	F(4)	F(5)
数组	0	1	1	2	3	5

2、若采用由底向上的迭代方法，自下而上的构建，通常由循环语句实现，可以避免采用递归函数时所带来的额外开销，如下代码，通过for()循环实现：

#include <stdio.h>
int main()
{int i, n;long long int f1 = 1, f2 = 1, f;		//初始值f1=f2=1printf("请输入要输出的斐波那契数列项数：");scanf("%d", &n);printf("斐波那契数列前%d项为：\n", n);printf("%lld %lld ", f1, f2);for (i = 3; i <= n; i++){f = f1 + f2;printf("%lld ", f);f1 = f2;f2 = f;}printf("\n");return 0;
}

（二）汉诺塔

首先，这里简单地以一个三层的汉诺塔，熟悉一下汉诺塔的游戏规则：一共有三根柱子，第一根柱子上有三个从上到下由小到大的圆盘，规定每次在三根柱子之间一次只能移动一个圆盘，且小圆盘上不能放大圆盘，试将第一根的三个圆盘移动到第三根柱子上。

点击链接可以试试，怎么让移动的次数最少？
汉诺塔可视化小游戏 Tower of Hanoi

最终的目的是完成的步数越少越好，我们可以很容易地得到三层的汉诺塔的最少移动步数为7次，移动过程中三个柱子共有8种不同的状态，如下：

同样的，四层的汉诺塔的最少移动步数为15次，而移动过程中三个柱子共有16种不同的状态：

五层的汉诺塔的最少移动步数为31次，而移动过程中三个柱子共有32种不同的状态：

……
通过数学归纳法，可得，当汉诺塔的层数为n时，最少的移动次数为 2^n-1次，移动过程中三个柱子共有2ⁿ 种不同的状态，其时间复杂度为O(2ⁿ) 。

• 汉诺塔问题的动态规划优化问题是通过带记忆的由顶向下法求解，即递归+可记忆，先解决小的问题，然后将问题的规模从小到大逐步扩大，最终得到问题的答案，且过程中避免了重复计算。【避免子问题重叠】

若以f[ n ]表示n个圆盘从TOWER 1移动到TOWER 3的最少步数，则f[1] = 1，即一个圆盘移动到TOWER 3的步数为1，而当n>1时，分析可知：

为了符合规则，需要先将一部分移动到TOWER 2上面，即有n-1个圆盘从TOWER 1经TOWER 3移动到TOWER 2上面，然后再将最大的圆盘移动到TOWER 3上面，由于TOWER 2已经是有序的，所以，需要将这n-1个圆盘从TOWER 2移动到TOWER 1，最终再移动到TOWER 3上。

可得，n个圆盘从TOWER 1移动到TOWER 3的最少步数为f[ n ]=f (n -1) + 1 + f (n - 1)=2f (n - 1)+1= 2^n-1+1，即T(n)= 2^n-1+1，所以时间复杂度为O(2ⁿ) 。

也可以从圆盘的数量来计算，按照规则，一个圆盘从TOWER 1移动到TOWER 3需要1步，两个圆盘从TOWER 1移动到TOWER 3需要3步（小的圆盘移动到中转点，再将大的圆盘移动到终点，最后将小的圆盘移动到终点），三个圆盘从TOWER 1移动到TOWER 3需要7步，……，n个圆盘从TOWER 1移动到TOWER 3需要3步 2^n-1步。

（三）最优二叉查找树

1、最优二叉查找树的定义
在n个不同关键字组成的有序序列中，每个关键字被查找的概率为p_i，通过关键字构造一棵的二叉查找树，它具有最小平均比较次数，即为最优二叉查找树（OBST），且左右子树也是最优二叉查找树，但最优二叉查找树不一定是高度最小的二叉查找树。
2、二叉查找树平均比较次数的计算
设有n=6个关键字的集合，各个实结点的查找概率分别为5：5%、2：30%、9：10%、0：3%、4：14%、6：25%，假设虚结点的查找概率分别为：e0：2%、e1：10%、e2：5%、e3：5%、e4：11%、e5：15%、e6：10%，计算二叉查找树的平均比较次数：

实结点：1×0.05+2×（0.3+0.1）+3×（0.03+0.14+0.25）=2.11；
虚结点：2×0.02+3×（0.1+0.05+0.05+0.11+0.15+0.1）=1.72，
即二叉查找树的平均比较次数为2.11+1.72=3.83。
3、最优子结构
最优二叉查找树中采用了动态规划的思想，分析其最优子结构：若一个二叉查找树是最优二叉查找树，可将其分为根结点、左子树和右子树，所以其左、右子树也是最优二叉查找树。
4、构建最优二叉查找树的分析
构建一个含n个关键字的最优二叉查找树的时间复杂度为O(n³)，由于通过使用二维数组，避免重复计算子树的最小权值和【避免子问题重叠】，从而提高了算法的效率，其空间复杂度为O(n²)。

（四）矩阵连乘

问题描述：在《线性代数》里面，学过矩阵的乘法，若干个矩阵相乘时，由于满足结合律，即(AB)C = A (BC)，可以通过加括号可以改变乘积的顺序，而结果不改变。若从相乘的计算量上来看，怎么让计算所需要的代价最少，即怎么通过加括号（改变乘积顺序），来使计算量最小，这是通过动态规划来优化问题的所在。

• 可将问题划分成两个子问题，即两个部分的矩阵相乘，分别对两个子问题进行递归求解，通过定义一个二维数组C[i][j]来表示第i个矩阵到第j个矩阵相乘的最小代价，以分界点k分割问题，对于两个子问题可分别表示为C[i][k]和C[k+1][j]，然后通过相同的方法继续进行递归求解，由于第i个矩阵的行数在p[i-1]，其列数在p[i]，所以递归式为C[i][j]=C[i][k]+C[k+1][j]+p[i-1]×p[k]×p[j]，该算法的时间复杂度取决于对所有矩阵求优解，即递归式上花费的时间，时间复杂度为O(n³)。

（五）0-1背包

问题描述：有n件物品，对某一物品i，其价值为V，重量为W，怎么选择将物品放入背包中，使得放入背包的物品的总价值最大，而动态规划就是来优化这个问题。

• 通过一个数组C[i][j]表示i个物品放入背包，此时背包容量为j所能得到的最大价值，由于当每个物品放入背包时，都要两种情况，能放进背包的要求是其所占重量要小于或等于当前背包剩余容量，即此时总价值为C[i-1][j-w_i]+v_i；不能放进背包的情况时，此时总价值为C[i-1][j]，然后通过这两种状态取最大值，即C[i][j]=Max{C[i-1][j]，C[i-1][j-w_i]+v_i}。由于得到的是背包的最大价值，设i=n、j=W，再通过一开始的最优解C[n][W]的值反推，确定放入背包的相应物品，即实现放入背包物品价值最大化，该算法的时间复杂度取决于物品个数n的一个for()循环语句和物品的重量W的一个for()循环语句，故其时间复杂度为O(nW)。