动态规划专题

4类典型的动态规划方程

如果子问题数目为O(nt),且每个子问题需要依赖于O(ne)个其他子问题,称这个问题为tD/eD的。

1D/1D型:定义一个实函数w(i,j)(1<=i<j<=n),已知D[0],状态转移方程为

  E[i] =min{D[i]+w(i,j)},0=<i<j,1=<j<=n————最长上升子序列

2D/0D型:已知D[i,0]和D[0,j] , 状态转移方程为:

  E[i,j]=min{D[i-1,j]+xi,D[i,j-1]+yi,D[i-1,j-1]+zi,j}————最长公共子序列

2D/1D型:————多源最短路径

2D/2D型:————双背包问题

对于这四种典型的方程,如果方程是tD/eD的,可以立刻得到一个最简单的时间复杂度为O(nt+e),空间复杂度为O(nt)的算法。很多情况下可以用滚动数组优化空间复杂度。

基本类型

1.数字三角形。有一个由非负整数组成的三角形,第一行只有一个数,除了最下行之外,每个数的左下方和右下方各有一个数。从第一行的数开始,每次可以往左下或者右下走一格,直到走到最下行,把沿途经过的数全部加起来。如何走,科室的这个和最大?

分析:设d(i,j)为从格子(i,j)出发能得到的最大和,则d(i,j)=a(i,j)+max{d(i+1,j),d(i+1,j+1)},边界是d(n+1,j)=0。

2.最长上升子序列(LIS)。给定n个整数A1,A2,...,An,按从左到右的顺序选出尽量多的整数,组成一个上升序列。

分析:设d(i)为以 i 结尾的最长上升子序列长度,则d(i)=max{0,d(j)|j<i,Aj<Ai}+1,最终答案是max{d(i)}。时间复杂度为O(n2)。

3.最长公共子序列问题(LCS)。给出两个子序列A和B,求长度最大的公共子序列。

分析:设d(i,j)为A1,A2,...,Ai和B1,B2,...,Bj的LCS长度,则当A[i]=A[j]时,d(i,j)=d(i-1,j-1)+1;否则,d(i,j)=max{d(i-1,j),d(i,j-1)},时间复杂度为O(nm)。

4.矩阵连乘(MCM)。给出n个矩阵组成的序列,设计一种方法把他们依次相乘,使得总运算量最小。假设第i个矩阵Aipi-1*pi的。

分析:设f(i,j)表示把Ai,Ai+1,...,Aj乘起来所需要的乘法次数,枚举“最后一次乘法”是第k个乘号,则f(i,j)=max{f(i,k)+f(k+1,j)+pi-1pkpj},边界是f(i,i)=0,时间复杂度为O(n3)

5.01背包问题

6.最优排序二叉树(OBST)

7.货郎担问题(TSP)

原文地址:https://www.cnblogs.com/acm-bingzi/p/3218896.html