动态规划数塔问题

动态规划经典问题---数塔问题132101443220有一个由正整数组成的三角形，第一行只有一个数，除了最下行之外每个数的左下方和右下方各有一个数，如下图所示。从第一行的数开始，每次可以往左下或右下走一格，直到走到三角形底层，把沿途经过的数全部加起来作为得分。如何走，使得这个得分最大？经典问题---数塔问题这是一个决策问题：每次选一个方向（左/右）行走。到底朝哪个方向走，取决于从左走能取到最大值还是从右走能取到最大值。最容易想到的是贪心算法：每次选择数字较大的方向走。

1----3---10----3，错误贪心法在此问题无法保证得到最优解。经典问题---数塔问题暴力搜索，列举出所有可能的路径再比较，得出和最大的路径。intd[100][100],n;intdfs(intx,inty)//x,y数组下标，函数返回从d[x][y]开始走到最后一层的最大和{ if(x==n)//边界条件 { returnd[x][y]; } else { intleft=dfs(x+1,y);//从左下方的数字开始能够得到的最大和 intright=dfs(x+1,y+1);//右下方能得到的最大和 returnd[x][y]+max(left,right); }}//main函数内调用dfs(1,1)经典问题---数塔问题暴力搜索存在大量重复计算在搜索的过程中以（3,2）为起点的子树搜索了两次。132410143220经典问题---数塔问题记忆化搜索，记忆数组f[x][y]存储(x,y)到数塔底层最大值，默认全为0intd[100][100],n,f[100][100];intdfs(intx,inty){ if(x==n) { returnd[x][y]; } elseif(f[x][y]!=0)returnf[x][y]; else { intleft=dfs(x+1,y); intright=dfs(x+1,y+1); f[x][y]=d[x][y]+max(left,right); returnf[x][y]; }}递推计算f[][]假设以格子(i,j)为首的“子三角形”的最大和为f[i][j]，则原问题的解是f[1][1]。从格子(i,j)出发往左走和往右走将分别到达位置(i+1,j)和(i+1,j+1)，则：

f[i][j]=d[i][j]+max(f[i+1][j],f[i+1][j+1]);f[1][1]=1+max(f[2][1],f[2][2]);f[2][1]=3+max(f[3][1],f[3][2]);f[2][2]=2+max(f[3][2],f[3][3]);递推计算从最底层开始，层层递进，最后得到最大值。时间复杂度为O(N^2)实际上d数组和f数组可以合并inti,j;for(j=1;j<=n;j++)f[n][j]=d[n][j];//最后一层for(i=n-1;i>=1;i--)//倒数第二层往上 for(j=1;j<=i;j++)

f[i][j]=d[i][j]+max(f[i+1][j],f[i+1][j+1]);另一种递推方式：f[i][j]表示从d[1][1]到达d[i][j]能够得到的路径总和的最大值，从左上方(i-1,j-1)和右上方(i-1,j)到达(i,j)则：

d[i][j]+max(f[i-1][j-1],f[i-1][j]) 1<j<i

f[i][j]=d[i][j]+f[i-1][j]; j=1

d[i][j]+f[i-1][j-1]; j=i从上往下计算，取max(f[n][i]),1<=i<=n动态规划原理在求解一个具体问题时，问题可以按时间顺序分解成若干相互联系的有顺序的阶段，在每一个阶段都要做出决策，全部过程的决策是一个决策序列，要使整个活动的总体效果达到最优的问题，称为多阶段决策问题。多阶段决策问题现有一张地图，各结点代表城市，两结点间连线代表道路，线上数字表示城市间的距离。如图所示，试找出从结点1到结点10的最短路径。

多阶段决策问题第一阶段第二阶段第三阶段第四阶段第五阶段F[i]表示结点i离结点10的最短距离那么，有F[i]=min(map[i][j]+F[j]),i->j存在有向边最后，求F[1]F[7]=3, F[8]=4, F[9]=6F[4]=6+F[9], F[5]=min(7+F[7],5+F[8]), F[6]=5+F[8]F[2]=min(1+F[4],5+F[5]), F[3]=min(4+F[5],3+F[6])F[1]=min(4+F[2],2+F[3])动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistepdecisionprocess)的优化问题时，提出了著名的最优化原理(principleofoptimality)，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著DynamicProgramming，这是该领域的第一本著作。动态规划的基本思想：和贪心类似的是，动态规划也是用来求解优化问题的。其基本思想也是将待求解问题分解成若干个子问题，但是经分解得到的子问题往往不是互相独立的（即有重叠子问题）。不同子问题的数目常常只有多项式量级。如果能够保存已经解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算。动态规划的实现思路：建立子问题的描述，建立状态间的转移关系，使用递推或记忆化搜索法来实现。状态定义：用问题的某些特征参数描述一个子问题。在“数塔问题”中用f[i][j]表示以格子(i,j)为根的子三角形的最大和。每个f[i][j]称为一个状态状态转移方程：即状态值之间的递推关系。这个方程通常需要考虑两个部分：一是递推的顺序，二是递归边界（也是递推起点）。从直接递归和后两种方法的比较可以看出：重叠子问题是动态规划展示威力的关键。动态规划的适用条件

适用动态规划的问题必须满足：最优化原理无后效性最优化原理（最优子结构性质）一个问题的最优解包含子问题的最优解，或者说通过子问题的最优解能够得到原问题的最优解，此问题具备最优子结构性质。最优化原理是动态规划的基础，任何问题，如果失去了最优化原理的支持，就不可能用动态规划方法计算。无后向性将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。动态规划的适用条件

数塔II132101443220有一个由正整数组成的三角形，第一行只有一个数，除了最下行之外每个数的左下方和右下方各有一个数,如下图所示。从第一行的数开始,除了某一次可以走到下一行的任意位置外,每次都只能左下或右下走一格,直到走到最下行,把沿途经过的数全部加起来.如何走,使得这个和尽量大?问题描述Input

输入数据首先包括一个整数C,表示测试实例的个数，每个测试实例的第一行是一个整数N(1<=N<=500)，表示数塔的高度，接下来用N行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间[0,99]内。Output

对于每个测试实例，输出可能得到的最大和。SampleInput

1

4

1

32

4101

43220SampleOutput

34

hint:路径1->3->10->20

问题分析面临的问题：第一行是可以移动到下一行任意位置，还是只能往左下或右下走一格？这取决解决这个子问题之前做过的事情。如果在第i行到第i+1行移动，已经任意移动过，那么就只能往左下或右下走一格了。所以这个问题，先前的决策可能会影响后续的决策，即状态定义有后效性。解决方法：扩展状态定义，把有后效性的部分包含进来。方法一假设从第一行到位置(i,j)，每次都只能往左下或右下走一格，令F1[i][j]为从第一行开始走到(i,j)所能得到的最大和；M1[i]表示从第一行走到第i行能够得到的最大值，M1[i]=max(F1[i][j]),1<=j<=i第i行到最后一行，又是每次都只能往左下或右下走一格，F2[i][j]表示从第i行第j列（即以（i,j)为根）开始走到最后一行所能得到的最大和；M2[i]表示从第i行到达最后一行能够的到的最大值，M2[i]=max(F2[i][j]),1<=j<=i则：

原问题的解为：max(M1[i]+M2[i+1])第i行到第i+1行任意移动枚举每一个i(i=1,2,3,...,n-1)，从而找到结果设以格子(i,j)为首的“子三角形”的最大和为f[i][j][k]

:k=1,则表示某一次可以走到下一行的任意位置k=0,则表示只能走左下或右下的一格，不可以任意移动则原问题的解是f[1][1][1]。

方法二数塔III132101443220有一个由正整数组成的三角形，第一行只有一个数，除了最下行之外每个数的左下方和右下方各有一个数,如下图所示。从第一行的数开始,每次都只能左下或右下走一格,直到走到最下行,把沿途经过的数全部加起来.如何走,使得这个和的个位数字尽量大?问题描述Input

输入数据首先包括一个整数C,表示测试实例的个数，每个测试实例的第一行是一个整数N(1<=N<=100)，表示数塔的高度，接下来用N行数字表示数塔，其中第i行有个i个整数，且所有的整数均在区间[0,99]内。Output

对于每个测试实例，输出可能得到的最大个位数。SampleInput

1

4

1

32

4101

43220SampleOutput

7

hint:路径1->3->10->3

问题分析面临的问题：两个数的个位数字加起来，得到的和可能变成两位数，因此全局最优解可能没有包含子问题的最优解，如上例：全局最优解f[1][1]为：5—0—4—0子问题f[2][1]的最优解：0—4—2全局最优解没有包含子问题的最优解

，该问题不满足最优子结构5000042000假设以格子(i,j)为根的“子三角形”走过的路径上所有数之和的个位数字最大为f[i][j]

i=2，f[2][1]=6，f[2][2]=0

i=1,

(f[2][1]+5)%10=1

(f[2][2]+5)%10=5

原问题的正确解为：f[1][1]=9

f[1][1]≠max{(f[2][1]+5)%10,(f[2][2]+5)%10}13210144322043208113237065453521746566扩展状态定义，设f[i][j][k]表示以格子(i,j)为根的“子三角形”是否存在所有数之和的个位数字为k(k=0,1,2,3,...,9)的路径：f[i][j][k]=1,则表示存在f[i][j][k]=0,则表示不存在则原问题的解是为：搜索满足f[1][1][k]==1的最大k，即为所求解问题分析1087数塔1318数塔II1319数塔III最长上升子序列

LIS（LongestIncreasingSubsequence）

给一个序列，求它的一个递增子序列，使它的元素个数尽量多。例如序列1,6,2,5,4,7的最长上升子序列是1,2,5,7162547DAG有向无环图a[i]<a[j]且i<j,则从a[i]向a[j]建一条有向边，求最长的路径f[i]表示以a[i]为结尾的最长的子序列的长度f[i]=max{f[j]}+1,(a[j]<a[i],j<i)f[1]=1,依次求解f[2],f[3]……..通过f[1],f[2],…..,f[i-1]求得f[i]，最后在所有f[]找一个最大值f[1],f[2],….f[i-1]f[i],f[i+1],….,f[n]已知（已经求出来）未知（还未求出来）1320拦截导弹1142魔族密码1233合唱队形1321难解的问题维护一个数组c，初始大小为1，c[i]表示最长上升子序列长度是i的所有子串中末尾最小的那个数，根据这个数字，只要当前的数比c[i]大，那么当前这个数一定能通过c[i]构成一个长度为i+1的上升子序列。在C数组中找一个尽量靠后的数字，这样我们得到的上升子串的长度最长，查找的时候使用二分搜索，这样时间复杂度便下降了1322雷曼兔1323笨笨的导弹攻击最长公共子序列问题(LCS)

问题描述一个给定序列的子序列是在该序列中删去若干元素后得到的序列。例如，序列Z=<B,C,D,B>是序列X=<A,B,C,B,D,A,B>的子序列，相应的递增下标序列为<2,3,5,7>。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。例如，若X=<A,B,C,B,D,A,B>和Y=<B,D,C,A,B,A>，则序列<B,C,A>是X和Y的一个公共子序列，序列<B,C,B,A>也是X和Y的一个公共子序列。而且，后者是X和Y的一个最长公共子序列，因为X和Y没有长度大于4的公共子序列。最长公共子序列(LCS)问题：给定两个序列X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>，要求找出X和Y的一个最长公共子序列。动态规划法解该问题：最长公共子序列问题有最优子结构性质，定理:LCS的最优子结构性质设：序列Xm=<x1,x2,…,xm>

Yn=<y1,y2,…,yn>

Xm和Yn的一个最长公共子序列Zk=<z1,z2,…,zk>，则：（1）若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序（2)若xm≠yn且zk≠xm

，则Zk是Xm-1和Yn的最长公共子序列；(3)若xm≠yn且zk≠yn

，则Zk是Xm和Yn-1的最长公共子序列。其中：Xm-1=<x1,x2,…,xm－１>，

Yn-1=<y1,y2,…,yn－１

>，

Zk-1=<z1,z2,…,zk－１>。最长公共子序列问题(LCS)

递归定义LCS的长度用c[i][j]记录序列Xi和Yj的最长公共子序列的长度。其中,Xi=<x1,x2,…,xi>，Yj=<y1,y2,…,yj>。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列，故c[i][j]=0。最长公共子序列问题(LCS)

c[i][j]=0c[i-1][j-1]+1max(c[i][j-1],c[i-1][j])i=0或j=0i，j>0且Xi=Yji，j>0且Xi!=Yj计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y):以序列X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>作为输入。输出两个数组c[][]和b[][]。其中c[i][j]存储Xi与Yj的最长公共子序列的长度，b[i][j]记录指示c[i][j]的值是由哪一个子问题的解达到的，这在构造最长公共子序列时要用到。X和Y的最长公共子序列的长度记录于c[m][n]中。voidLCS_LENGTH(X,Y){

for(i=1;i<=m;i++)c[i][0]=0;for(j=1;j<=n;j++)c[0][j]=0;

for(i=1;i<=m;i++)

for(j=1;j<=n;j++)

if

(x[i]==y[j]){c[i][j]=c[i-1][j-1]+1;b[i][j]=‘↖’;}elseif(c[i-1][j]≥c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=‘↑’;}else{c[i][j]=c[i][j-1];b[i][j]=‘←’}

}由于每个数组单元的计算耗费Ο(1)时间，算法LCS_LENGTH耗时Ο(mn)。最长公共子序列问题(LCS)

最长公共子序列问题(LCS)

构造最长公共子序列由算法LCS_LENGTH计算得到的数组b可用于快速构造序列X=<x1,x2,…,xm>和Y=<y1,y2,…,yn>的最长公共子序列。首先从b[m][n]开始，沿着其中的箭头所指的方向在数组b中搜索。当b[i][j]中遇到"↖"时，表示Xi与Yj的最长公共子序列是由Xi-1与Yj-1的最长公共子序列在尾部加上xi得到的子序列；当b[i][j]中遇到"↑"时，表示Xi与Yj的最长公共子序列和Xi-1与Yj的最长公共子序列相同；当b[i][j]中遇到"←"时，表示Xi与Yj的最长公共子序列和Xi与Yj-1的最长公共子序列相同。最长公共子序列问题(LCS)

算法LCS(b,X,i,j)实现根据b的内容打印出Xi与Yj的最长公共子序列。voidLCS(b,X,i,j){

ifi==0orj==0return;

ifb[i][j]==‘↖’{LCS(b,X,i-1,j-1);print(x[i]);/*打印x[i]*/

}

elseifb[i,j]==‘↑’LCS(b,X,i-1,j)elseLCS(b,X,i,j-1);}在算法LCS中，每一次的递归调用使i或j减1，因此算法的计算时间为O(m+n)。最长公共子序列问题(LCS)

背包问题有N个物品和一个背包，其中:物品具有重量(w1,w2,…,wn)背包的最大重量承受限制为W

每件物品要么选要么不选，怎样使背包尽可能装满，求装入背包物品重量和的最大值?简单方法：定义标记数组f，初始全部为0，f[i]=1表示存在物品重量和为i的选取方案f[0]=1;//不选任何物品for(intj=1;j<=n;j++)//w1,w2,w3,……

for(inti=W-w[j];i>=0;i--)//总和不能超过背包容量

{ if(f[i])//存在重量和为i的方案

f[i+w[j]]=1;//加上第j个物品

}为了保证，每个物品最多只取一次，代码中第二层for循环，循环变量必须是递减的如果改成for(inti=0;i<=W-w[j];i++)，可能导致某件物品选了多次比如，W=10，w[1]=3，那么f[3]=1，i循环到3时，f[6]又等于1，第1件物品取了两次背包问题有N个物品和一个背包，其中:物品具有重量(w1,w2,…,wn)和价值(p1,p2,…,pn)背包的最大重量承受限制为W

如何放置物品可得最高价值?简单方法：数组f，初始全为0f[i]表示物品重量和为i的方案总价值的最大值f[i]=0表示不存在重量和为i的选取方案for(intj=0;j<n;j++){ for(inti=W-w[j];i>=0;i--) { if(f[i]>0||i==0) { if(f[i+w[j]]<f[i]+p[j])//存在重量和为i+w[j]，总价值更高的方案 f[i+w[j]]=f[i]+p[j]; } }}//在f数组内选一个最大值w[]={5,3,2}P[]={9,7,8}W=53，5，0编号，剩下的重量，总价值2，5，0Depthfirstleftfirst决策树1，5，01，2，7-，5，0-，0，92，3，81，3，81，0，15-，2，7-，3，8左边-不选右边-选intMaxVal(inti,intr)//返回前i个物品，剩余重量是r，能取得的价值最大值{if(i==1)//边界条件{if(r>=w[i])returnp[i];//选第一个物品elsereturn0;}if(r<w[i])returnMaxVal(i-1,r);//只能往左returnmax(MaxVal(i-1,r),p[i]+MaxVal(i-1,r-w[i]));

//在不选第i个物品与选择第i个物品中选一个最大值}记忆化搜索：intMaxVal(inti,intr){ if(i==1) { if(r>=w[i])returnp[i]; elsereturn0; } if(f[i][r])returnf[i][r]; if(r<w[i])f[i][r]=MaxVal