动态规划

1动态规划电子科技大学齐朋辉2数字三角形•7•38•810•2744•45265•从第一层走到最后一层，每次向左下或右下走，求路径的最大权值和。3解法•设f[i][j]表示从第i行第j个点到底部的路径权值和的最大值f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j]4如何求解•如果转移方程？•观察方程的性质•因为第i行的解要由第i+1行的解得到，所以必须从下向上转移！！5如何求解•最后一行怎么处理？•f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j]•i=n时，i+1行是非法状态•边界条件，特殊处理即可。•i=n:f[i][j]=a[i]][j]6代码展示for(inti=1;i=n;i++)//初始化边界f[n][i]=a[n][i];//转移顺序很重要for(inti=n-1;i0;i--)for(intj=1;j=i;j++)dp[i][j]=max(dp[i+1][j+1],dp[i+1][j])+a[i][j];7要点•状态定义：如何描述一个子问题？•定义要明确。•状态转移方程：如何由子问题构造出原问题的解？•边界条件、初始条件•递推顺序8数字三角形II132410143220•从第一层走到最后一层，每次向左下或右下走，求路径的最大权值和。•某一层可以随意跳9解法•加一维状态•记f[i][j][k]为以(i,j)为顶点的子问题的解，k=1表示可以随意跳，k=0表示不能随意跳。•原问题的解即为f[1][1][1]•转移方程？10数字三角形III132410143220•从第一层走到最后一层，每次向左下或右下走，求路径的权值和的个位数的最大值11解法•之前的定义是否可行？•如何转移？•f[i][j]=max{f[i+1][j],f[i+1][j+1]}+a[i][j]•f[i][j]=•(max{f[i+1][j],f[i+1][j+1]}+a[i][j])mod10•f[i][j]=max{(f[i+1][j]+a[i][j])mod10,(f[i+1][j+1]+a[i][j])mod10}12解法•之前的定义是否可行？•记f[i][j][k]为，以(i,j)为起点走到底部，路径权值和的个位数是否有可能等于k•如何转移？•对于每一个(i,j)，枚举k，遍历所有状态即可13总结•算法设计–状态定义–状态转移（递推顺序有时很重要）–边界条件、初始条件•条件–无后效性–最优子结构14滑雪为了获得速度，滑雪的路径必须向下倾斜，每次可以向上下左右4个方向滑行。区域由一个二维数组给出，每个数字代表该点的高度。求滑行的最长距离。1234516171819615242520714232221813121110915困难？•能用刚才数字三角形的方法做么？–哪里不能？–没有明确的依赖顺序，无法直接用递推进行转移•解决办法–记忆化搜索16Fibonacci数列•把递归过程中的值记录下来，这样就能保证每个值只算一次。F[0]=F[1]=1;for(inti=2;i=n;++i)F[i]=-1;intFib(intn){if(F[n]!=-1)returnF[n];F[n]=Fib(n-1)+Fib(n-2);returnF[n];}17滑雪的记忆化搜索实现18再次总结•如何利用转移方程求解–递推–递归–求解通项公式•如何看待记忆化–避免大量重复计算–简洁明了，方便理解–递推比较繁琐，或没有明确的依赖顺序（图）1919经典模型2001背包•在n件物品取出若干件放在空间为V的背包里，每件物品的体积为w1，w2……wn，与之相对应的价值为p1,p2……pn。2101背包•定义状态f[i][j]：•考虑前i件物品，选的物品总体积=j的情况下价值和的最大值•转移方程：O(n*V)f[i][j]=max(f[i-1][j],f[i-1][j-wi]+pi)•初始条件：f[0][0]=0,f[0][j0]=-INF•答案：max(f[n][j=V])2201背包•定义状态f[i][j]：•考虑前i件物品，选的物品总体积=j的情况下价值和的最大值•转移方程：O(n*V)f[i][j]=max(f[i-1][j],f[i-1][j-wi]+pi)•初始条件：f[0][j=V]=0•答案：f[n][V]23完全背包•有n种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的体积是w，价值是p。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。24完全背包•定义状态dp[i][j]：•考虑前i件物品，选的物品总体积=j的情况下价值和的最大值•转移方程：O(n*V*V/W)dp[i][j]=max(dp[i-1][j-wi*k]+pi*k)(k=0)•初始条件：dp[0][0]=0,dp[0][j0]=-INF•答案：max(dp[n][j=V])25多重背包•有n种物品和一个容量为V的背包，每种物品都有一个数量限制l。第i种物品的体积是w，价值是p。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。26背包问题•分组背包•二维背包•树上的背包•注：完全背包和多重背包都是可以优化到O(n*V)的，参考《背包问题九讲》27LIS•一个数列S如果分别是已知数列的单调上升子序列，且是所有符合此条件序列中最长的，则S称为已知序列的最长上升子序列。求S。28LIS•定义状态dp[i]：•表示以S[i]结尾的最长上升子序列的长度•转移方程：O(n*n)dp[i]=max(dp[j]+1)(ji&&S[j]S[i])29LIS•定义状态dp[S[i]]：•表示以S[i]结尾的最长上升子序列的长度•转移方程：dp[S[i]]=max(dp[v]+1)(vS[i])•复杂度？O(n*n)•用线段树或者树状数组优化？O(n*logn)30LCS•一个数列S如果分别是两个已知数列A，B的子序列，且是所有符合此条件序列中最长的，则S称为已知序列的最长公共子序列。求S。31LCS•定义状态dp[i][j]：•表示考虑A的前i位和B的前j位，最长公共子序列的长度•转移方程：O(|A|*|B|)if(A[i]==B[j])dp[i][j]=dp[i-1][j-1]+1;elsedp[i][j]=max(dp[i-1][j],dp[i][j-1]);3232几种常见的题型33动态规划•区间DP•按位DP•树形DP•状压DP34•用二进制记录DP的状态•利用二进制运算进行转移•与，或，非，异或•与1010&1100=1000•或1010|1100=1110•非~1010=0101•异或1010^1100=0110状态压缩DP35埋雷给一个n*m的矩阵，某些格子可以放雷，任意两个雷不能相邻，问有多少种放法。Sample239111010n,m=12CDOJ88236埋雷dp[i][j]代表处理到第i行，这一行上的雷的摆放情况用j的二进制表示，的方案有多少转移时，先用这一行的雷的状态|下一行的不能放的位置的状态，取反后就是能放的位置的状态，枚举这个状态的合法子集进行转移。如何判断一个子集合不合法=判断一个二进制数有没有两个相邻的137and给你N个数，对于每个数输出N个数里与它相与为0的最大的数，不存在输出0Sample216989816N=1000000ai1000000CDOJ60338and正难则反：一个数A，取反为B，对于C，如果A&C=0,则有C|B=B39and对于初始的每个数dp[num[i]]=num[i]转移dp[i]=max(dp[i],dp[j])j为i的二进制删掉任意一个1得到的数最后对于原来的每个数，取反后找dp的最大值即可402048Flappy2048有一个栈，最开始没东西，现在过来了很多2,4,8,16，路过每个值的时候你可以将其加入栈中，并得到这么多的分数，如果栈顶的两个值相同，他们会合并成一个新的值，为他们的和，并得到这么多的分数。问你如何选择能使分数最大4284834N=500ZOJ3802412048N=500，所以栈中最大的数只有500*16512*16=8192，并且都是2的幂并且栈中只有最后一个单调递减序列有可能被合并。Dp[i][j]代表，选到第i个数，栈中最后一个单调递减序列的状态是j，能得到的最大分数是多少分这个数选或不选转移即可42按位DP-数位统计问题•求区间[A,B]之间满足某种性质的个数(最值)•1=A,B=10^18•例：求区间[A,B]间恰有K个8的数的个数•[1,100]K=2ans=1•[1,100]K=1ans=18•[1,100]K=0ans=81•如果是求个数ret[A,B]=ret[1,B]-ret[1,A-1]43按位DP-数位统计问题•cnt[L][K]表示长度为L且恰含K个8的数的个数•包含前导0•cnt[1][1]=1,cnt[1][0]=9;•如何计算[1,3981],K=1?•首位为1,2的数2*cnt[3][1]•前两位为30-38的数8*cnt[2][1]+1*cnt[2][0];•前三位为390-397的数8*cnt[1][1]•前四位为3981的数cnt[0][0];•首位为0的四位数cnt[3][1]44按位DP-数位统计问题•按位DP核心思想：•由高位到低位•高位取前缀，枚举当前位，低位任意取•低位任意取DP预处理45按位DP-数位统计问题•如何求cnt[L][K]?•cnt[0][0]=1;cnt[0][i]=0(i0)•cnt[L][K]=cnt[L-1][K]*9+cnt[L-1][K-1];46Windy数定义windy数：相邻数字的差至少是2的数，例如10不是windy数，而13是windy数。求给定区间中有多少windy数。区间端点范围为[1,2000000000]SCOI200947Windy数显然这是一个按位DP按位DP整体思想：由高位到低位枚举当前位，高位的数取前缀，低位的数预处理[A,B]=[1,B]–[1,A-1]我们先看代码48Windy数49Windy数50Windy数按位DP要特别注意两个问题calc(n)求出的答案0是否被计算在内，n是否被计算在内前导0我的习惯：不计算nans[l,r]=calc(r+1)–calc(l)0是否计算在内完全看心情。。51Lucky给定L,R,X,Y输出[L,R]中，含有X个6，Y个8的第K大的数1=L=R=1e1852Lucky先求出L之前的所有合法数H然后二分，求[1,x]中恰好有K+H个合法数的x即可53Bit给定M,K，求一个N，使得N+1,N+2,…N+N中，二进制包含恰好K个1的数恰好有M个Sample(110,111,1000,1001,1010)325CF413D54Bit满足二分性！对于N+1,N+2,…N+N和N+2,N+3,…,N+N+1,N+N+2下面的序列少了个N+1，多了2N+1和2N+2但是如果N+1满足条件，2N+2一定也满足条件所以N越大越有可能满足条件，所以直接二分然后DP55Beautifulnumber求[L,R]区间内能被自己的每一位非0的数整除的数。例如132就是合法的Sample112152CF55D56Beautifulnumber如何记录出现了的数字？如何记录是否能整除出现了的数字？57Beautifulnumberdp[L][i][j]代表，长度不超过L的数，出现过的数字的状态为i，模2520的值为j的方案数0=i256,0=j2520预处理：O(18*10*256*2520)对于每一个查询，高位取前缀，枚举当前位，再枚举低位出现过的数字，这样就可以知道低位模2520的合法值有哪些查询：O(18*10*256)5858例题选讲59稳住GCD•给n个数的序列，问最多删掉多少数，使得序列的gcd不变•1=n=700•1=ai=10000CDOJ92360稳住GCD•Dp[i][j]