提高篇动态规划专题

1、提高篇动态规划专题动态规划 递归递归 递推递推一种精妙的算法思想。特点： 没有固定的写法 具体问题具体分析需要： 多练习、多思考、多总结什么是动态规划最优化问题1 1复杂问题2 2分解子问题3 3记录每个解4 4dynamic programming 动态规划是一种用来解决一类最优化问题最优化问题的算法思想。将一个复复杂的问题杂的问题分解成若干个子问题子问题，通过综合子问题的最优解来得到原问题的最优解。动态规划会将每个求解过的子问题的解记录下来解记录下来，这样可以提高计算效率，但不不能说这种做法就是是动态规划的核心核心。动态规划的递归写法【理解】如何记录子问题的解，来避免下次遇到相同的子问题时

2、的重复计算。斐波那契数列：f0=1,f1=1,fn=fn-1+fn-2(n=2)int f(int n) if (n=0|n=1) return 1; else return f(n-1)+f(n-2); 一般可以使用递归或者递推的写法来实现动态规划，其中递归写法在此处又称作记忆化搜索记忆化搜索。缺点：重复计算。当n=5时，f(5)=f(4)+f(3),接下来计算f(4)=f(3)+f(2),这样f(3)就被计算了两次。如果n很大，时间复杂度会高达o(2n)。避免重复计算 开一个一维数组dp，用于保存已经计算过的结果，其中dpn记录f(n)的结果，并用dpn=-1表示f(n)当前还没有被计算过

3、。int dpmaxn;int f(int n) if (n=0|n=1) return 1; /递归边界 if (dpn!=-1) return dpn; /已经计算过，直接返回结果，不再重复计算 else dpn=f(n-1)+f(n-2); /计算f(n)，并保存至dpn return dpn; /返回f(n)的结果 记忆化搜索记忆化搜索时间复杂度时间复杂度o(2n)降到了降到了o(n)时间复杂度对比图f(5)f(4)f(3)f(2)f(1)f(0)f(1)f(2)f(1)f(0)f(3)f(2)f(1)f(0)f(1)斐波那契数列递归图o(2n)f(5)f(4)f(3)f(2)f(1)

4、f(0)f(1)f(2)f(3)斐波那契数列记忆化搜索o(n)重叠子问题（overlapping subproblems） 如果一个问题可以被分解为若干个子问题，且这些子问题会重复出现，那么就称这个问题拥有重叠子问题。 一个问题必须拥有重叠子问题重叠子问题，才能使用动态规划动态规划去解决。动态规划的递推写法【数塔问题】将一些数字排成数塔的形状，其中第一层有一个数字，第二层有两个数字第n层有n个数字。现在要从第一层走到第n层，每次只能走向下一层连接的两个数字中的一个，问：最后将路径上所有数字相加后得到的和最大是多少？5837124910516113694动态规划的递推写法 如果开一个二维数组f，

5、其中fij存放第i层的第j个数字，那么就有f11=5,f21=8,f22=3,f31=12,f54=9,f55=4。 如果尝试穷举所有路径，然后记录路径上的数字和的最大值，那么由于每层中的每个数字都会有两条分支路径，因此时间复杂度为o(2n)，这在n很大的情况下是不可以接受的。那么，产生这么大复杂度的原因原因是什么？ 从5出发，按587的路线来到7，并枚举从从7出发的到达最底层的所有路径出发的到达最底层的所有路径。但是，之后当按537的路线再次来到7时，又会去枚举从从7出发的到达最底层的出发的到达最底层的所有路径所有路径，这就导致了从从7出发的到达最底层的所有路径出发的到达最底层的所有路径都被

6、反复反复地访问。其实，可以把路径上能产生的最大和记录下来，这样就可以避免重复计算。 所以令dpij表示从第i行第j个数字出发的到达最底层的所有路径中能得到的最大和，例如dp32就是7的最大和。那么dp11就是最终答案，现在想办法求求出出它。 注意一个细节：如果要求出“从位置（1,1）到达最底层的最大和”dp11，那么一定要先求出它的两个子问题“从位置（2,1）到达最底层的最大和dp21”和“从位置（2,2）到达最底层的最大和dp22”，即进行了一次决策决策：走数字5的左下还是右下。于是dp11就是dp21和dp22的较大值加上5。公式：dp11=max(dp21,dp22)+f11动态规划的递

7、推写法 归纳：如果要求出dpij，那么一定要求出它的两个子问题“从位置(i+1,j)到达最底层的最大和dpi+1j”和“从位置(i+1,j+1)到达最底层的最大和dpi+1j+1”，即进行了一次决策决策：走位置(i,j)的左下还是右下。公式：dpij=max(dpi+1j,dpi+1j+1)+fij 把dpij称为问题的状态状态，公式称为状态转移方程状态转移方程，它把状态dpij转移为dpi+1j和dpi+1j+1。可以发现，状态dpij只与第i+1层的状态有关，而与其他层的状态无关。那么如果总是将层号增大，什么时候会到头呢？其实，数塔的最后一层的dp值总是等于元素本身，即dpnj=fnj(1

8、=j=n)，把这种可以直接确定其结果的部分称为边界边界，而动态规划的递推递推写法总是从这些边界出发，通过状态转移方程扩散到整个dp数组。 这样就可以从最底层各位置的dp值开始，不断往上上求出每一层各位置的dp值，最后就会得到dp11，即为想要的答案。动态规划的递推写法（代码）#include#includeusing namespace std;const int maxn=1000;int fmaxnmaxn,dpmaxnmaxn;int main() int n; cinn; for(int i=1;i=n;i+) for(int j=1;jfij; /输入数塔 for(int j=1;j

9、=1;i-) for(int j=1;j=i;j+) dpij=max(dpi+1j,dpi+1j+1)+fij; /动态转移方程 coutdp11endl;return 0; 动态规划的递推写法 输入数据558 312 7 164 10 11 69 5 3 9 4 输出结果44动态规划的递推写法对比递归和递推写法：递归递归也可实现（即从dp11开始递归，直至到达边界时返回结果）。是自顶向下自顶向下（top-down approach），即从目标问题开始，将它分解成子问题的组合，直到分解至边界为止。递推递推是从底向上从底向上（bottom-up approach），即从边界开始，不断向上解决问

10、题，直到解决了目标问题。概念概念：如果一个问题的最优解可以由其子问题的最优解有效地构造出来，那么称这个问题拥有最优子结构最优子结构（optimal substructure）。可以使用动态规划的条件一个问题必须拥有重叠子问题重叠子问题和最优子结构最优子结构，才能使用动态规划动态规划去解决。分治与动态规划 相同点：将问题分解为子问题，然后合并子问题的解得到原问题的解。 不同点：分治分治的子问题不重叠不重叠。动态规划动态规划的问题拥有重叠重叠子问题。例如：归并排序和快速排序都分别处理左序列和右序列，然后将左右序列的结果合并，过程中不出现重叠子问题，因此他们使用的都是分治法。另外，分治法解决的问题不

11、一定是最优化问题，而动态规划解决的问题一定是最优化问题。贪心与动态规划 相同点：要求原问题必须有最优子结构。 不同点：贪心法的计算方式“自顶向下”，但并不等待子问题求解完毕后再选择使用哪一个，而是通过一种策略直接选择一个子问题去求解，没被选择的子问题直接抛弃。这种所谓“最优选择”的正确性需要用归纳法证明。而动态规划不管是采用自底向上还是自顶向下的计算方式，都是从边界开始向上得到目标问题的解（即考虑所有子问题）。贪心：壮士断腕的决策，只要选择，绝不后悔。贪心：壮士断腕的决策，只要选择，绝不后悔。动态规划：要看哪个选择笑到最后，暂时领先说明不了问题。动态规划：要看哪个选择笑到最后，暂时领先说明不了

12、问题。最大连续子序列和【问题描述】 给定一个数字序列a1,a2,an,求i,j(1=i=j=n),使得ai+aj最大，输出这个最大和。【样例】输入：-2 11 -4 13 -5 -2输出：20步骤1：令状态dpi表示以ai作为末尾的连续序列的最大和（ai必须作为末尾）。那么dp0=-2 dp1=11 dp2=7 (11+(-4)=7) dp3=20 (11+(-4)+13=20) dp4=15 (11+(-4)+13+(-5)=15) dp5=13 (11+(-4)+13+(-5)+(-2)=13)于是转换成求dp0,dp1,dpn-1中的最大值，想办法求解dp数组。原序列：原序列：-2 11

13、 -4 13 -5 -2步骤2：因为dpi以ai结尾的连续序列，那么只有两种情况： 这个最大和的连续序列只有一个元素，即ai。dpi=ai 这个最大和的连续序列有多个元素，即从前面某处ap开始(pi)，一直到ai结尾。dpi=dpi-1+ai 状态转移方程：状态转移方程：dpi=maxai,dpi-1+ai 边界dp0=a0，从小到大枚举i，即可得到整个dp数组。#include#include#include#includeusing namespace std;const int maxn=10010;int amaxn,dpmaxn;/ai存放序列，dpi存放以ai结尾的连续序列的最大和

14、int main() int n; scanf(%d,&n);/cinn; for(int i=0;iai; /边界 dp0=a0; for(int i=1;in;i+) /状态转移方程 dpi=max(ai,dpi-1+ai); /dpi存放以ai结尾的连续序列的最大和，需要遍历i得到最大的才是结果 int k=0; for(int i=1;idpk) k=i; printf(%dn,dpk);/coutdpk)endl; system(pause); return 0;状态的无后效性 当前状态记录了历史信息，一旦当前状态确定，就不会再改变，且未来的决策只能在已有的一个或若干个状态的基础上进

15、行，历史信息只能通过已有的状态去影响未来的决策。 即每次计算状态dpi，都只会设计dpi-1，而不直接用到dpi-1蕴含的历史信息。动态规划核心 对动态规划可解的问题来说，总会有很多设计状态的方式，但并不是所有状态都具但并不是所有状态都具有无后效性有无后效性，因此必须设计一个拥有无后效性的状态以及相应的状态转移方程，否则动态规划就没有办法得到正确结果。事实上，如何设计状态和状态转移方程，才如何设计状态和状态转移方程，才是动态规划的核心，而它们也是动态规划是动态规划的核心，而它们也是动态规划最难的地方最难的地方。问题 a: 最大连续子序列（时间限制: 1 sec 内存限制: 32 mb）题目描述

16、给定k个整数的序列 n1, n2, ., nk ，其任意连续子序列可表示为 ni, ni+1, ., nj ，其中 1 = i = j = k。最大连续子序列是所有连续子序列中元素和最大的一个，例如给定序列 -2, 11, -4, 13, -5, -2 ，其最大连续子序列为 11, -4, 13 ，最大和为20。现在增加一个要求，即还需要输出该子序列的第一个和最后一个元素。输入测试输入包含若干测试用例，每个测试用例占2行，第1行给出正整数k( k= 10000 )，第2行给出k个整数，中间用空格分隔，每个数的绝对值不超过100。当k为0时，输入结束，该用例不被处理。输出对每个测试用例，在1行里

17、输出最大和、最大连续子序列的第一个和最后一个元素，中间用空格分隔。如果最大连续子序列不唯一，则输出序号i和j最小的那个（如输入样例的第2、3组）。若所有k个元素都是负数，则定义其最大和为0，输出整个序列的首尾元素。 样例输入 5 -3 9 -2 5 -4 3 -2 -3 -1 0 样例输出 12 9 5 0 -2 -1提示（较难） 首先可以想到的做法是枚举每个区间的和，预处理sumi来表示区间1, i的和之后通过减法我们可以o(1)时间获得区间i, j的和，因此这个做法的时间复杂度为o(n2)。 然后这题的数据范围较大，因此还需作进一步优化才可以ac。记第i个元素为ai，定义dpi表示以下标i

18、结尾的区间的最大和，那么dpi的计算有2种选择，一种是含有ai-1，一种是不含有ai-1，前者的最大值为dpi-1+ai，后者的最大值为ai。而两者取舍的区别在于dpi-1是否大于0。最长不下降子序列（lis）【问题描述】 在一个数字序列中，找到一个最长的子序列（可以不连续），使得这个子序列是不下降（非递减）的。【样例】输入：8 1 2 3 -1 -2 7 9输出：5（长度）/即1 2 3 7 9 令dpi表示以ai结尾的最长不下降子序列长度（和最大连续子序列和问题一样，以ai结尾是强制的要求）。这样对ai俩说就会有两种可能：（1）如果存在ai之前的元素sj(ji)，使得ajdpi（即把ai跟

19、在以aj结尾的lis后面时能比当前以ai结尾的lis长度更长），那么就把ai跟在以aj结尾的lis后面，形成一条更长的不下降子序列（令dpi=dpj+1）。（2）如果ai之前的元素都比ai大，那么ai就只好自己形成一条lis，但是长度为1，即这个子序列里面只有一个ai。最后以ai结尾的lis长度就是（1）（2）中能形成的最大长度。状态转移方程 dpi=max1,dpj+1(j=1,2,i-1&ajai)其中隐含了边界：dpi=1(1=i=n)时间复杂度o(n2)#include#includeusing namespace std;const int n=100;int an,dpn;int

20、main() int n; cinn; for(int i=1;iai;int ans=-1; /记录最大的dpi for(int i=1;i=n;i+) /按顺序计算出dpi的值 dpi=1; /边界初始条件（即先假设每个元素自成一个子序列） for(int j=1;j=aj&(dpj+1dpi) dpi=dpj+1; /状态转移方程，用以更新dpi ans=max(ans,dpi); coutansendl; return 0;问题 a: 最长上升子序列（ 2 sec 64 mb）题目描述一个数列ai如果满足条件a1 a2 . an，那么它是一个有序的上升数列。我们取数列(a1, a2,

21、., an)的任一子序列(ai1, ai2, ., aik)使得1 = i1 i2 . ik = n。例如，数列(1, 7, 3, 5, 9, 4, 8)的有序上升子序列，像(1, 7)， (3, 4, 8)和许多其他的子序列。在所有的子序列中，最长的上升子序列的长度是4，如(1, 3, 5, 8)。 现在你要写一个程序，从给出的数列中找到它的最长上升子序列。输入输入包含两行，第一行只有一个整数n（1 = n = 1000），表示数列的长度。第二行有n个自然数ai，0 = ai = 10000，两个数之间用空格隔开。输出输出只有一行，包含一个整数，表示最长上升子序列的长度。样例输入7 1 7

22、3 5 9 4 8样例输出4最长公共子序列（lcs） 给定两个字符串（或数字序列）a和b，求一个字符串，使得这个字符串是a和b的最长公共部分（子序列可以不连续）。 样例： 如样例所示，字符串“sadstory”与“adminsorry”的最长公共子序列为“adsory”，长度为6。 令dpij表示字符串a的i号位和字符串b的j号位之前的lcs长度（下标从1开始），如dp45表示“sads”与“admin”的lcs长度。那么可以根据ai和bj的情况，分为两种决策：（1）若ai=bj，则字符串a与字符串b的lcs增加了1位，即有dpij=dpi-1j-1+1。（2）若ai!=bj，则字符串a的i号位和字符串b的j号位之前的lcs无法延长，因此dpij将会继承dpi-1j与dpij-1中的较大值，即有dpij=maxdpi-aj，dpij-1。状态转移方程： 边界：dpi0=dp0j=0(0=i=n,0=i=m)时间复杂度：o(nm)输入数据：sadstoryadminsorry输出结果：6最长回文子串给出一个字符串s，求s的最长回文子串的长度。样例：字符串“patzjujztaccbcc”的最长回文子串为“atzjujzta”，长度为9。最长回文子串是否能转换为最长公共子序列（是否能转换为最长公共子序列（