动态规划例题选讲

动态规划例题选讲刘宸亨[e-mail]例题1路径问题•给一个N*M的方格图，从左上角(0,0)走到右下角(N,M)，每次只能向右或者向下走，问一共有多少种路径？例题1路径问题•用F[i][j]表示从起点走到位置(i,j)时的路径总数，那么转移方程如下：F[i][j]=F[i–1][j]//从(i-1,j)走过来+F[i][j–1]//从(i,j–1)走过来O(NM)的状态数，O(1)的转移，总的时间复杂度为O(NM)。例题2路径问题2•给一个N*M的方格图，从左上角(0,0)走到右下角(N,M)，每次只能向右、向下或者向右下走，问一共有多少种路径？例题2路径问题2•本题较上题来说多了一个走法：向右下走，只需要在转移方程中再加上F[i–1][j–1]即可。更多的路径问题•路径问题还有很多变种：诸如：1.有些格子有障碍不能走，一共有多少种方案？2.每个格子有一个数字，问走出的最大数字和是多少？以上问题留作思考题。例题3序列问题•给一个长度为N的序列A[],求最大的子段和是多少？•例如N=5•A[]={-1,2,-3,4,5}•答案为9，即{4,5}这一段。例题3序列问题•用F[i]表示以i结尾的最大子段和，那么有F[i]=F[i–1]+A[i]当F[i–1]+a[i]0时0当F[i–1]+a[i]=0时当F[i–1]+a[i]0时，留下部分和可能导致之后的结果更好，当F[i–1]+a[i]=0时，无论之后的和再大，加上一个负数只会令和减小，故舍去。例题3序列问题•复杂度分析：•状态总数为O(N)，O(1)的转移，总的时间复杂度为O(N)。•作业：完成poj1050例题4最长上升子序列问题•给一个长度为N的序列A[]，求出其中的最长上升子序列的长度。•例如N=5•A[]={2,1,4,3,5}•答案为3，序列是{2,4,5},{2,3,5},{1,4,5},{1,3,5}例题4最长上升子序列问题•用F[i]表示以a[i]结尾的最长上升子序列的长度，那么有F[i]=max{F[j]+1,1=ji&&a[j]a[i]}对于状态i来说，它可以接到所有的在它之前的并且比它小的数的后面构成上升子序列，所以我们要枚举状态j进行转移。时间复杂度为O(N^2)。例题4最长上升子序列问题•有没有更好的做法呢？•答案是有的！例题4最长上升子序列问题•观察转移方程F[i]=max{F[j]+1,1=ji&&a[j]a[i]}•我们发现对于i之前的状态j，只需要查找满足小于a[i]的最大的F[j]即可，我们可以维护一颗线段树，即可在O(logN)的时间复杂度内完成一次转移，总的时间复杂度是O(NlogN)。例题4最长上升子序列问题•另外还有贪心的做法，利用到二分查找，时间复杂度同样是O(NlogN)。•简单提示：对于长度同样为k的上升子序列，最后一个数越小，今后越有可能导致最优解。•如{1,2}和{1,4}，同样长度为2，但是{1,2}比{1,4}好，假如后面有个3……•留作思考题。•作业：完成poj2533例题50/1背包问题•有N个物品，每个物品i的重量是W[i]，问你一个可以载重M的背包，最多可以装多少个物品？•例如N=5•W={1,2,3,4,5}•M=3•可以装{1,2}也可以装{3}，但是装最多的物品是装{1,2}，总共2个物品。例题50/1背包问题•首先必须指出，背包问题是NP难的。但是当规模一定时，我们可以用动态规划来求解。•令F[i]表示重量和为i的背包最多可以装多少个物品，那么有F[i]=max{F[i–W[j]]+1}枚举放第j个物品例题50/1背包问题•很遗憾，这个算法是错的，每个物品只有一个，这样进行方程转移会导致一个物品放入背包多次：假设最优状态的获得为F[i]=F[i–W[j]]+1而F[i–W[j]]=f[i–W[j]–W[j]]+1例题50/1背包问题•刚才的方程在每个物品有无限多个的时候成立，那么每个物品只有一个怎么办呢？•我们可以首先枚举物品W[j]，•然后倒向把重量从大到小枚举•方程还是采取刚才的形式，那么利用W[j]更新的A[i–W[j]]不会去更新A[i]，于是问题解决。例题50/1背包问题•代码如下：F[0]=0;for(intj=0;jN;++j)for(inti=M;i=0;--i)if(i–W[j]=0&&F[i–W[j]]+1F[i])F[i]=F[i–W[j]]+1;时间复杂度为O(NM)。作业：完成poj3624例题6最长公共子序列问题•给两个序列A[],B[]，长度分别是N和M，求他们的最长公共子序列。•例如A[]={1,2,3,4,5},B[]={1,4,3,5}•那么它们的最长公共子序列为{1,3,5}，长度是3。例题6最长公共子序列问题•令F[i][j]表示第一个序列取1~i，第二个序列取1~j，它们的最长公共子序列是多少，那么有F[i][j]=F[i–1][j–1]+1，当A[i]=B[j]时max{F[i–1][j],F[i][j–1]}，其他情况当A[i]=B[j]时，那么最长公共子序列为1~i-1与1~j-1的最长公共子序列加上A[i]=B[j]这对构成，否则的话要么丢弃A[i]要么丢弃B[j]。时间复杂度为O(NM)。作业：完成poj1458Bit-DP•Bit-DP又名集合DP，状态没有先前看到的例题那么直观，通常来说是使用一个二进制数来表示状态，0表示没有，1表示有，或者0表示偶数，1表示奇数。近年来这类题目出现的频率比较大。最显著的特点是当你看到题目数据规模不太大时，可以往这方面想。例题7汉密顿路问题•给一个图有N(N=10)点，a[i][j]表示点i到点j的边权，-1表示不能走，问走出的最短的汉密顿路的长度是多少？例题7汉密顿路问题•令F[mask][i]表示当前已经走过的点集为mask，最后一个到达的点为i的最段路径，这里mask是一个N位二进制数，如10101表示点1，3，5是已经走过的，2，4是没有走过的，那么方程转移如下：F[mask][i]=max{F[mask’][j]+a[i][j]}当a[i][j]不为-1，且mask’等于mask中把i的1置为0，如mask=10101，则所有的mask’为00101,10001,10100。例题7汉密顿路问题•复杂度分析：•状态数为O(N*2^N)，转移为O(N)，总的时间复杂度为O(N^2*2^N)。•作业：完成POJ2288例题8匹配问题•给一张图，adj[i][j]为1时表示点i,j之间有边相连，求最大匹配数目。•图中点数=10。例题8匹配问题•这题是一个一般图最大基数匹配问题，使用Edmond-Karp算法可以在O(N^3)的时间复杂度内求解，但是算法很复杂，而且没有利用到题目点数少的性质。例题8匹配问题•在这里我们采取集合DP的方式来求解，令F[mask]表示已匹配的点集为mask的最大匹配数，其中mask为2进制数，0表示未匹配，1表示匹配，那么有F[mask]=max{F[mask–2^i–2^j]+adj[i][j]}其中mask中的第i位和第j为为1。例题8匹配问题•复杂度分析：•状态数为O(2^N)，转移为O(N^2)，总的时间复杂度为O(N^2*2^N)。例题9中国邮路问题•给一个图，a[i][j]表示点i到点j的距离，一个邮递员从点1开始走，要求每个点至少走一次，并且最后回到起点1，问最小距离为多少？例题9中国邮路问题•通过分析我们知道，邮递员走的路径其实是一条欧拉回路，并且权最小。例题9中国邮路问题•我们首先看一个简单一点的问题：•添加最少的边使得原图中存在欧拉回路。例题9中国邮路问题•一个图存在欧拉回路当且仅当它的所有点的度为偶数。•有了如上的性质，我们发现：如果度为奇数的点有奇数个，那么问题无解。•否则可以两两拿出来匹配即可。例题9中国邮路问题•回到本问题，我们首先通过最短路算法求出所有度为奇数的点之间的最短路，设为d[i][j]。•然后进行集合DP，状态F[mask]表示度状态为mask的最小费用，mask是一个二进制数，其中1表示度为奇数，0表示度为偶数，那么有F[mask]=max{F[mask-2^i-2^j]+d[i][j]}其中mask包含i和j，且i和j为奇度点。例题9中国邮路问题•显然，最后答案为F[0]。•复杂度分析：•状态数为O(2^N)，转移为O(N^2)，总的时间复杂度为O(N^2*2^N)。•作业：完成poj2404例题10两条路径问题•回忆问题1，我们要从左上角走到右下角，走2条不想交的路径（起点终点除外），问有多少种方法。例题10两条路径问题•令F[i][j][x][y]表示第一条路走到了(i,j)，第二条路走到了(x,y)的方案数，那么转移方法易得。•留作课后思考。•复杂度O(NMNM)。例题10两条路径问题•其实可以做到更优美，注意到两条路同时走的时候，i+j=x+y，于是可以少记录y，令y=i+j-x即可。复杂度变成O(NMM)。•作业：完成=1097谢谢大家！