Chapter 15 Author：Single Rush Dynamic programming —— 动态规划 Date : 2017.3.24

动态规划DP

动态规划，是求解最优化问题的一种方法，将一个问题分成一个个子问题，将每次求解时重叠子问题进行记录，这样每个子问题只需要求解一次，极大地减小了时间复杂度，因此也被称为记忆化搜索，但与搜索又有着截然不同的本征。 如何用动态规划解题，本文将结合《算法导论》与一些典型题型做简单分析。

在《算法导论》中有这么一段描述：

我们通常按如下4个步骤来设计一个动态规划算法： 1. 刻画一个最优解的结构特征。 2. 递归地定义最优解的值。 3. 计算最优解的值，通常采用自底向上的方法。 4. 利用计算出的信息构造一个最优解。

步骤1～3是动态规划算法求解问题的基础。如果我们仅仅需要一个最优解的值，而非解本身，可以忽略步骤4，如果确实要做步骤4，有时就需要在执行步骤3的过程中维护一些额外信息，以便来构造一个最优解。

在我们平时的解题过程中，往往是先设置状态量，而后定义状态转移方程，最后采用自底向上的方法计算最优解，其实正是上面所说的步骤1～3，而步骤4则遇到较少。

首先，我们例举一个常见的DP题——杭电HDU ACM 2084 数塔。这一题可以帮助我们了解什么是动态规划，如何构造最优解的结构（状态量），动态规划如何求解最优解（状态转移方程），为什么求得的解是最优解。 有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？ 如何用动态规划求解这一问题呢？ 首先，我们构造一个状态量： dp[i][j] 代表从第i+1层第j+1个数往下走所得数字之和的最大值。则最优解的结构（即最优解的状态量）为 dp[0][0] 第1层第1个数往下走所得数字之和的最大值，也就是我们要求的从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大的解。 然后，如何求解，我们定义状态转移方程：

dp[i−1][j]=num[i−1][j]+(dp[i][j]>dp[i][j+1]?dp[i][j]:dp[i][j+1]); 最后，我们通过for循环，自底向上计算。 C语言实现：

memset(dp, 0, sizeof(dp)); for(i=n;i>0;i--) for(j=0;j<i;j++) dp[i-1][j]=num[i-1][j]+(dp[i][j]>dp[i][j+1]?dp[i][j]:dp[i][j+1]); printf("%d\n",dp[0][0]);//最终结果

最终， dp[0][0] 所代表的第1层第1个数往下走所得数字之和的最大值，即为此题所需求的数字之和最大值。当然也有其他方法计算这一题。

---

动态规划，个人感觉，其实，是一种记忆化搜索，类似于数学归纳法。 构造好结构后，动态规划的最终解是不是最优解： 1.最初状态是最初状态最优解。 2.假设k状态是k状态最优解，通过状态转移方程可推得K+1状态，并且证明K+1状态也是K+1状态最优解。 即证最终状态，即最终解，是最优解。

---

由于在《算法导论》上没有看到有关背包问题的讲解，但背包又是入门DP的一大经典题型，想要学习DP的码友可以Du娘《背包九讲》，我认为写得比较不错，但是有很多地方还需要补充。另外，简单的旅行商问题也可以使用DP来做，如果规模大，计算最优解可能难度较高，可以使用如遗传算法等计算一个较优解。

---

15.1 钢条切割

钢条长度对应的价格表：

长度i12345678910价格p1589101717202430

构造最优结构： r[i] 代表i英寸长度的最优价格。 初始状态量： r[1]=1 ； 状态转移方程： r[n]=max(p[n],r[1]+r[n−1],r[2]+r[n−2],...) ； 最终状态量： r[N] ；

public class cut_rod { int[] p={0,1,5,8,9,10,17,17,20,24,30}; int CUT_ROD(int n){ int[] r=new int[100]; r[0]=0; for(int j=1; j<=n; j++){ int q; if(j<=10) q=p[j]; else q=0; for(int i=1; i<=(j/2); i++){ q=q>(r[i]+r[j-i])?q:(r[i]+r[j-i]); } r[j]=q; } return r[n]; } }

15.2 矩阵链乘法（矩阵连乘法）

解释说明，如第一种方式 (A(B(CD))) ：CD数乘的次数为 40∗30∗5=6000 ，CD结构=40×5，而后 B(CD) 数乘次数为 10∗40∗5=2000 ，B(CD)结构=10×5，最后 A(B(CD)) 数乘次数为 50∗10∗5=2500 ，最终结果为 6000+2000+2500=10500 。 假定输入为 p[0],p[1],p[2],...,p[n] ，其中， A[i] 的规模是 p[i−1]×p[i] 。 构造结构： m[i][j] 即为从第i个矩阵连乘至第j个矩阵所需要的最少数乘次数。 初始状态量： m[i][i]=0 状态转移方程：

m[i][j]=min{m[i][j],m[i][k]+m[k+1][j]+p[i−1]∗p[k]∗p[j]} 最终状态量： m[1][n] 即为所需求的最少数乘次数。

public class Matrix_Chain { public static final int MAX_VALUE = 2<<30-1; void matrix_chain(int[] p){ int[][] matrix = new int[100][100]; int n = p.length - 1; for(int i=1; i<=n; i++){ matrix[i][i]=0; } for(int l=2; l<=n; l++){ for(int i=1; i<=n-l+1; i++){ int j=i+l-1; matrix[i][j]=MAX_VALUE; for(int k=i; k<j; k++){ int q = matrix[i][k]+matrix[k+1][j]+p[i-1]*p[k]*p[j]; if(q<matrix[i][j]){ matrix[i][j]=q; System.out.println(i+","+j+"---->"+matrix[i][j]); } } } } } }

15.4 最长公共子序列

15.5 最优二叉搜索树

补充

状态压缩DP

例：旅行商问题（TSP） 某售货员要到若干城市去推销商品，已知各城市之间的旅费。要选一条路程，从驻地出发，经每个城市一遍，最后回到驻地，使得总旅费最小。 设G=(V,E)是一个带权图G，旅行售货员问题要找图G的费用（权）最小的一条回路。Notice that 旅行商从1开始。 如上图所示： 1<−>2 的费用是30， 1<−>3 的费用是6， 1<−>4 的费用是4， 2<−>3 的费用是5， 2<−>4 的费用是10。 构造结构时，首先需要对状态量进行压缩，如二进制压缩，将旅行商去过的点记录下来，用二进制中的第i位是否为1代表旅行商是否去过第i个点。如0010即代表旅行商去过点2，1011即代表旅行商去过点1、2、4。 v[i][j] 代表从点i到点j的费用。 构造的结构： tsp[vis][i] 代表旅行商去过点的记录为vis，目前在第i点。 初始状态量： tsp[0][1] ，代表还未去过任何城市，目前在点1。 状态转移方程：

tsp[vis|2j−1][j]=min{tsp[vis|2j−1][j],tsp[vis][i]+v[i][j]}(点i与点j连接) 最终状态量： tsp[15][1] ，注意15的二进制表示为1111，代表旅行商去过1,2,3,4点目前在点1。

概率与期望DP

轮廓线DP

Floyd算法

未完待续

CONTACT ME