简介

在这篇blog中我将通过费氏数列引入，然后介绍动态规划的概念，以及它和分治苏纳法的区别与联系。然后使用动态规划的思想来解决以下四个非常著名的问题：

• 矩阵连乘
• 平面凸多边形最优三角划分
• 背包问题
• 最长公共子序列

同时也是为了自己做记录，防止以后自己忘记。

引例

费氏数列是由0，1开始，之后的每一项等于前两项之和：
0，1，1，2，3，5，8，13，21，34，55，89，144…

递归方法：

但是存在效率较低的问题：

因为存在大量的重复计算，比如说，如上图所示，f(n-4)就出现了多次计算的情况。

动态规划算法

借助中间变量存储结果，然后就可以消除重复计算。

伪代码：

算法主要思想：

动态规划&分治算法

区别

• 动态规划主要用于优化问题，求解最优解问题。
• 子问题并不独立，存在重复的子问题。

个人理解

我认为，我所见过的大多数动态规划问题似乎都用到了我们常说的的空间换时间和分治的思想。

• 复杂问题分解为小问题去解决，这是和分治法有相同思路的地方
• 用空间存储中间变量，消除重复计算

总结

动态规划问题

矩阵连乘

问题实例

这里借用我们上课的时候老师给的例子，可以很明显的看到，这里不同的矩阵相乘的顺序得到的最终的时间复杂度师有很大不同的。我们目标是找到时间复杂度最低的连乘次数。

穷举法

这种方法的时间复杂度非常高，完全是指数级别的，具体的推导这里不在赘述。

动态规划求解

思路：
计算A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和A[k+1:j]的次序也是最优的

矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。

建立递归关系：
计算A[i:j]，1≤i≤j≤n，所需要的最少数乘次数C[i,j]，则原问题的最优值为C[1,n]

• 当i=j时，A[i:j]=Ai，因此，C[i,i]=0，i=1,2,…,n
• 当i<j时，设k为最优断开点
  
  我们递归的定义：
  
  复杂度分析
  
  如果这里看不太懂，可以先看后面的伪代码和示例。

伪代码：

实战应用：

平面凸多边形最优三角划分

问题描述

平面凸多边形 弦：连接平面多边形的任意两个不同顶点的线段。
平面凸多边形：如果一个平面多边形的任意一条弦，要么在该多边形的内部，要么恰好为该多变形的边，那么，称该平面多边形为凸的。否则，称该平面多变形为凹的

三角划分 将平面凸多边形分割成互不相交的三角形。

平面凸多边形的表示：用平面凸多边形顶点的逆时针序列表示凸多边形，即P={v0, v1,…,vn}表示具有n＋1条边的平面凸多边形。

动态规划解法

这里类比上一个矩阵连乘的解法，归纳如下：
若P ={v0, v1,…,vn}是一个凸多边形，那么{vi-1,vi,…,vj}所构成的必定也是一个凸多边形。定义C[i,j] 为子凸多边形{vi-1,vi
,…,vj}的最优三角划分所对应的权函数值，即其最优值。

对于上述C的推导式，可以完全套用矩阵连乘思想。

背包问题

问题描述

给定n个物品{u1,u2,…,un}和一个背包，物品i 的重量为wi，价值为vi，已知背包的承重量为C。
问：在不撑破背包的条件下，选择哪些物品装入背包，得到的总价值最大？

动态规划解法

伪代码：

实例

背包的承重量为C=9；给定4个物品，重量(w)分别为2，3，4，5；价值(v)依次为3，4，5，7。问：背包中最多能装的物品的总价值是对少？

最长公共子序列

问题描述

给定两个定义在字符集∑上的字符串A和 B，长度分别为n和m，现在要求它们的最长公共子序列的长度值(最优值)，以及 对应的子序列(最优解) 。

动态规划解法

我们假设C[i, j ]表示的是A字符串的前i个，j表示 B字符串的前j个中的最长公共子序列。所以我们可以得到：

伪代码：

实例

问题

解法：

总结

判断是否动态规划问题

当面对一个问题是可以归纳或者转换为最优问题的时候我们应该首先考虑以下两点：

• 是否存在最优子结构
• 是否存在子问题重复计算
• 子问题是可解的低复杂问题

如果满足上面的两点，基本上可以使用动态规划进行求解。

求解思路

1. 最优解一定包含最优子问题，最优解一定由最优子结构组成
2. 空间换时间，存储中间变量，消除子问题冗余计算

参考我们老师部分PPT内容，转载请注明
大家共勉~~