动态规划总结经典题目(经典中的经典)

《动态规划总结经典题目(经典中的经典)》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、动态规划总结——经典问题总结本文着重讨论状态是如何表示，以及方程是怎样表示的。当然，还附上关键的，有可能作为模板的代码段。但有的代码的实现是优化版的。经典问题总结t长上升子序列(LIS)问题描述如下：设L=是n个不同的实数的序列，L的递增子序列是这样一个子序列Lin=，其屮kl〈k2〈…〈km且aKl〈ak2〈…〈akm。求最大的m值。这里采用的是逆向思维的方法，从最后一个开始想起，即先从A[N](A数组是存放数据的数组，下同)开始，则只有长度为1的子序列，到A[N-1]时就有两种情况，如果a[n-l]〈a[n]则

2、存在长度为2的不下降子序列a[n_l],a[n];如果a[n-l]>a[n]则存在长度为1的不下降子序列a[n_l]或者a[n]。有了以上的思想，DP方程就呼之欲出了(这里是顺序推的，不是逆序的)：DP[I]=MAX(1,DP[J]+1)J=O，1，...，I-1但这样的想法实现起来是)0(r<2)的。本题还有更好的解法，就是O(n*l0gn)。利用了长升子序列的性质來优化，以下是优化版的代码：//最长不降子序constintSIZE=500001;intdata[STZE];intdp[SIZE];//返冋值是最长不降子序列的最大长度,复杂度0(N*logN)int

3、LCS(intn){//N是DATA数组的长度，下标从1开始intlen(l),low,high,mid,i;dp[l]=data[l];for(i=l;i<=n;++i){low=l;high=len;while(1ow<=high){//二分mid=(1ow+high)/2;if(data[i]〉dp[mid]){low=mid+1;}else{high=mid-1;})dp[lo'v]=data[i];if(low>len){++len;}}return1en;}t长公共子序列(LCS)给出两个字符串b,求它们的最长、连续的公共字串。这很容易就想到以DP[T][

4、J]表示A串匹配到bB串匹配到J时的最大长度。则：0I:二0

5、

6、J=0DP[I][J]=DP[I-1][J-1]+1A[I]==B[J]MAX(DP[I-1][J],DP[I][J-1])不是以上情况但这样实现起来的空间复杂度为O(rf2),而上面的方程只与第1-1行冇关，所以可以用两个一维数组来代替。以下是代码：//最长公共子序列constintS1ZE=1OO1;intdp[2][STZE];//两个一维数组//输入两个字符串，返冋最大的长度intLCS(conststring^a,conststring^b){inti,j,flag;memset(dp,0,si

7、zeof(dp));flag=l;for(i=l;i<=a.sizeO;++i){for(j=l;j<=b.sizeO;++j){if(a[i-l]==b[j-l])dpEflag]Ej]=dp[l-flag][j-l]+l;elsedptflag][j]=.MAX(dpEflag][j-1],dp[卜flag][j]);}f]ag=l-flag;}returndp[1-flag][b.sizeO];}有N件物品和一个容量力V的背包。第i件物品的大小是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。用DP[I][J]表示前I件物品放入一个容S为J的背

8、包可以获得的最大价值。则DP[I][J]=DP[I-1][J]，J

9、DP[V]=-1(即非法状态)intPackct(intn，intv){inti，j;mcmsct(dp,0,sizcof(dp));for(i=l;i<=n;++i){for(j=v;j>=c[i];-j){//这里是倒序，别弄错了dp[j]=MAX(dp[j],dp[j-c[i]]+w[i]);returndp[v];}完全背包问题有N种物品和一个容量为V的背包，每种物品都荇无限件可川。第i种物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容景，且价伉总和最大O很容易可以得到这种状态表示：用DP[I][