提高篇——动态规划专题

提高篇——动态规划专题动态规划•递归递推一种精妙的算法思想。特点：没有固定的写法具体问题具体分析需要：多练习、多思考、多总结什么是动态规划最优化问题1复杂问题2分解子问题3记录每个解4DynamicProgramming动态规划是一种用来解决一类最优化问题的算法思想。将一个复杂的问题分解成若干个子问题，通过综合子问题的最优解来得到原问题的最优解。动态规划会将每个求解过的子问题的解记录下来，这样可以提高计算效率，但不能说这种做法就是动态规划的核心。动态规划的递归写法【理解】如何记录子问题的解，来避免下次遇到相同的子问题时的重复计算。斐波那契数列：F0=1,F1=1,Fn=Fn-1+Fn-2(n=2)intF(intn){if(n==0||n==1)return1;elsereturnF(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，用于保存已经计算过的结果，其中dp[n]记录F(n)的结果，并用dp[n]=-1表示F(n)当前还没有被计算过。intdp[maxn];intF(intn){if(n==0||n==1)return1;//递归边界if(dp[n]!=-1)returndp[n];//已经计算过，直接返回结果，不再重复计算else{dp[n]=F(n-1)+F(n-2);//计算F(n)，并保存至dp[n]returndp[n];//返回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)F(0)F(1)F(2)F(3)斐波那契数列记忆化搜索O(n)重叠子问题（OverlappingSubproblems）•如果一个问题可以被分解为若干个子问题，且这些子问题会重复出现，那么就称这个问题拥有重叠子问题。•一个问题必须拥有重叠子问题，才能使用动态规划去解决。动态规划的递推写法【数塔问题】将一些数字排成数塔的形状，其中第一层有一个数字，第二层有两个数字……第n层有n个数字。现在要从第一层走到第n层，每次只能走向下一层连接的两个数字中的一个，问：最后将路径上所有数字相加后得到的和最大是多少？5837124910516113694动态规划的递推写法如果开一个二维数组f，其中f[i][j]存放第i层的第j个数字，那么就有f[1][1]=5,f[2][1]=8,f[2][2]=3,f[3][1]=12,……,f[5][4]=9,f[5][5]=4。如果尝试穷举所有路径，然后记录路径上的数字和的最大值，那么由于每层中的每个数字都会有两条分支路径，因此时间复杂度为O(2n)，这在n很大的情况下是不可以接受的。那么，产生这么大复杂度的原因是什么？从5出发，按587的路线来到7，并枚举从7出发的到达最底层的所有路径。但是，之后当按537的路线再次来到7时，又会去枚举从7出发的到达最底层的所有路径，这就导致了从7出发的到达最底层的所有路径都被反复地访问。其实，可以把路径上能产生的最大和记录下来，这样就可以避免重复计算。所以令dp[i][j]表示从第i行第j个数字出发的到达最底层的所有路径中能得到的最大和，例如dp[3][2]就是7的最大和。那么dp[1][1]就是最终答案，现在想办法求出它。注意一个细节：如果要求出“从位置（1,1）到达最底层的最大和”dp[1][1]，那么一定要先求出它的两个子问题“从位置（2,1）到达最底层的最大和dp[2][1]”和“从位置（2,2）到达最底层的最大和dp[2][2]”，即进行了一次决策：走数字5的左下还是右下。于是dp[1][1]就是dp[2][1]和dp[2][2]的较大值加上5。公式：dp[1][1]=max(dp[2][1],dp[2][2])+f[1][1]动态规划的递推写法归纳：如果要求出dp[i][j]，那么一定要求出它的两个子问题“从位置(i+1,j)到达最底层的最大和dp[i+1][j]”和“从位置(i+1,j+1)到达最底层的最大和dp[i+1][j+1]”，即进行了一次决策：走位置(i,j)的左下还是右下。公式：dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+f[i][j]把dp[i][j]称为问题的状态，公式称为状态转移方程，它把状态dp[i][j]转移为dp[i+1][j]和dp[i+1][j+1]。可以发现，状态dp[i][j]只与第i+1层的状态有关，而与其他层的状态无关。那么如果总是将层号增大，什么时候会到头呢？其实，数塔的最后一层的dp值总是等于元素本身，即dp[n][j]==f[n][j](1=j=n)，把这种可以直接确定其结果的部分称为边界，而动态规划的递推写法总是从这些边界出发，通过状态转移方程扩散到整个dp数组。这样就可以从最底层各位置的dp值开始，不断往上求出每一层各位置的dp值，最后就会得到dp[1][1]，即为想要的答案。动态规划的递推写法（代码）#includecstdio#includealgorithmusingnamespacestd;constintmaxn=1000;intf[maxn][maxn],dp[maxn][maxn];intmain(){intn;cinn;for(inti=1;i=n;i++){for(intj=1;j=I;j++){cinf[i][j];}//输入数塔}for(intj=1;j=n;j++){dp[n][j]=f[n][j];}//边界for(inti=n-1;i=1;i--){for(intj=1;j=i;j++){dp[i][j]=max(dp[i+1][j],dp[i+1][j+1])+f[i][j];}//动态转移方程}coutdp[1][1]endl;return0;}动态规划的递推写法•输入数据55831271641011695394•输出结果44动态规划的递推写法•对比递归和递推写法：•递归也可实现（即从dp[1][1]开始递归，直至到达边界时返回结果）。是自顶向下（Top-downApproach），即从目标问题开始，将它分解成子问题的组合，直到分解至边界为止。•递推是从底向上（Bottom-upApproach），即从边界开始，不断向上解决问题，直到解决了目标问题。概念：如果一个问题的最优解可以由其子问题的最优解有效地构造出来，那么称这个问题拥有最优子结构（OptimalSubstructure）。可以使用动态规划的条件一个问题必须拥有重叠子问题和最优子结构，才能使用动态规划去解决。分治与动态规划•相同点：将问题分解为子问题，然后合并子问题的解得到原问题的解。•不同点：分治的子问题不重叠。动态规划的问题拥有重叠子问题。例如：归并排序和快速排序都分别处理左序列和右序列，然后将左右序列的结果合并，过程中不出现重叠子问题，因此他们使用的都是分治法。另外，分治法解决的问题不一定是最优化问题，而动态规划解决的问题一定是最优化问题。贪心与动态规划•相同点：要求原问题必须有最优子结构。•不同点：贪心法的计算方式“自顶向下”，但并不等待子问题求解完毕后再选择使用哪一个，而是通过一种策略直接选择一个子问题去求解，没被选择的子问题直接抛弃。这种所谓“最优选择”的正确性需要用归纳法证明。而动态规划不管是采用自底向上还是自顶向下的计算方式，都是从边界开始向上得到目标问题的解（即考虑所有子问题）。•贪心：壮士断腕的决策，只要选择，绝不后悔。•动态规划：要看哪个选择笑到最后，暂时领先说明不了问题。最大连续子序列和【问题描述】给定一个数字序列A1,A2,……,An,求i,j(1=i=j=n),使得Ai+……+Aj最大，输出这个最大和。【样例】输入：-211-413-5-2输出：20步骤1：令状态dp[i]表示以A[i]作为末尾的连续序列的最大和（A[i]必须作为末尾）。那么dp[0]=-2dp[1]=11dp[2]=7(11+(-4)=7)dp[3]=20(11+(-4)+13=20)dp[4]=15(11+(-4)+13+(-5)=15)dp[5]=13(11+(-4)+13+(-5)+(-2)=13)于是转换成求dp[0],dp[1],…,dp[n-1]中的最大值，想办法求解dp数组。原序列：-211-413-5-2步骤2：因为dp[i]以A[i]结尾的连续序列，那么只有两种情况：•这个最大和的连续序列只有一个元素，即A[i]。dp[i]=A[i]•这个最大和的连续序列有多个元素，即从前面某处A[p]开始(pi)，一直到A[i]结尾。dp[i]=dp[i-1]+A[i]•状态转移方程：dp[i]=max{A[i],dp[i-1]+A[i]}•边界dp[0]=A[0]，从小到大枚举i，即可得到整个dp数组。#includecstdio#includealgorithm#includecstdlib#includeiostreamusingnamespacestd;constintmaxn=10010;intA[maxn],dp[maxn];//A[i]存放序列，dp[i]存放以A[i]结尾的连续序列的最大和intmain(){intn;scanf(%d,&n);//cinn;for(inti=0;in;i++){//读入序列scanf(%d,&A[i]);//cina[i];}//边界dp[0]=A[0];for(inti=1;in;i++){//状态转移方程dp[i]=max(A[i],dp[i-1]+A[i]);}//dp[i]存放以A[i]结尾的连续序列的最大和，需要遍历i得到最大的才是结果intk=0;for(inti=1;in;i++){if(dp[i]dp[k]){k=i;}}printf(%d\n,dp[k]);//coutdp[k])endl;system(pause);return0;}状态的无后效性•当前状态记录了历史信息，一旦当前状态确定，就不会再改变，且未来的决策只能在已有的一个或若干个状态的基础上进行，历史信息只能通过已有的状态去影响未来的决策。•即每次计算状态dp[i]，都只会设计dp[i-1]，而不直接用到dp[i-1]蕴含的历史信息。动态规划核心•对动态规划可解的问题来说，总会有很多设计状态的方式，但并不是所有状态都具有无后效性，因此必须设计一个拥有无后效性的状态以及相应的状态转移方程，否则动态规划就没有办法得到正确结果。事实上，如何设计状态和状态转移方程，才是动态规划的核心，而它们也是动态规划最难的地方。问题A:最大连续子序列（时间限制:1Sec内存限制:32MB）•题目描述•给定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行里输出最大和、最大连续子序列的第一个和最后一个元素，中间用空格分隔。如果最大连续子序列不唯一，则输出序号i和j最小的那个（如输入样例的第2、3组）。若所有