动态规划设计从入门到精通(Ⅰ).ppt

LCS 定义状态dp[i][j]： 表示考虑A的前i位和B的前j位且最后一位为B[j]的最长公共子序列的长度 转移方程：O(|A|*|B|) if(A[i]==B[j]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=dp[i][j-1]; 代码展示 LIS 一个数列S如果分别是已知数列的单调上升子序列，且是所有符合此条件序列中最长的，则S称为已知序列的最长上升子序列。求S。 LIS 定义状态dp[i]： 表示以S[i]结尾的最长上升子序列的长度 转移方程：O(n*n) dp[i]=max{dp[j]+1}jiS[j]S[i] 代码展示 那么n=1e5? LIS 定义状态dp[i]： 表示以S[i]结尾的最长上升子序列的长度 转移方程： dp[i]=max(k),f[k-1]S[i]=f[k] f[k]=min(S[l]),dp[l]=k f[k]单调上升可以二分找到位置k 时间nlogn 代码展示 单调队列优化 能将N维dp降优化至N-1维 朴素算法超时 考虑能否单调队列优化 dp[i]=max(f(k))+g(i),ki且g(i)与k无关 LCIS 一个数列S如果分别是两个已知数列A，B的子序列，且是上升序列的所有符合此条件序列中最长的，则S称为已知序列的最长公共上升子序列。求S。 LCIS 定义状态dp[i][j]： 表示考虑A的前i位和B的前j位且最后一位为B[j]的最长公共子序列的长度 转移方程： dp[i][j]=dp[i][j-1],a[i]!=b[j] dp[i][j]=max{dp[i-1][k]}+1，a[i]=b[j],b[k]b[j],kj 时间n^3 代码展示 能不能更快？ LCIS dp[i][j]=max{dp[i-1][k]}+1，a[i]=b[j],b[k]b[j],kj ∴a[i]b[k] 那么对于每个a[i]，令 maxdp=dp[i-1][j]，a[i]b[j] dp[i][j]=maxdp+1 时间n^2 代码展示 * Thankyou * * * 动态规划入门到精通(Ⅰ) 一些前话——xiper 做了专题，感觉自己很强，然后比赛还是什么DP都做不来（有很多时候压根就没看出来是DP），正常吗？ 正常，一般来讲新人（没有基础的）刚开始时没有建立起DP思维，即便做了专题，短时间内肯定还是云里雾里的，导致比赛的时候写不出DP，同时DP本身就难，大爷们都不一定次次能出DP，更不要说新人了 怎么快速入门，能又快又准的写出基础的DP（套路DP题） 掌握基本的写法，理解经典模型的转移 搞个数字三角形 从上往下走，每次可以向左下或右下走一个，直到最下行，问经过数字的和最大是多少？ 13 11 11 12 7 36 6 14 15 8 12 7 13 24 11 朴素贪心 13+？左？右？ 不说更多，显然在第二行已经迷失方向 13 11 11 12 7 36 6 14 15 8 12 7 13 24 11 如何求解 如果利用转移方程求解原问题？ f[i][j]=max(f[i-1][j],f[i-1][j-1]) +a[i][j] 1、从上向下转移，即i从小到大？ 2、从下向上转移，即i从大到小？ 观察转移方程的性质 因为第i行的解要由第i-1行的解得到，所以必须从上向下转移 如何求解 边界条件，特殊处理即可。 j=1:f[i][j]=a[i][j]+f[i-1][j] j=i:f[i][j]=a[i][j]+f[i-1][j-1] 代码展示 for(int i=2;i=n;i++)//初始化边界 f[i][1]=a[i][1]+f[i][1]; for(int i=2;i=n;i++)//初始化边界 f[i][i]=a[i][i]+f[i][i-1]; for(int i=3;i=n;i++) for(intj=1;j=m;j++) f[i][j]=max(f[i-1][j], f[i][j-1])+a[i][j] 更多选择？ 有了转移方程 f[i][j]=max(f[i-1][j],f[i-1][j-1])+a[i][j] 容易得dfs(i,j)=max(dfs(i-1,j),dfs(i-1,j)) 时间？ 可以使用数组f[i][j]= dfs(i,j) 记忆化有哪些信誉好的足球投注网站 代码展示 memset(f,-1,sizeof f) int dfs(int i,int j) if(f[i][j])return f[i][j]=max(dfs(i-1,j-1),dfs(i-1,j)); return f[i][j]; 为何还要记忆化有哪些信誉好的足球投注网站？ 滑雪 为了获得速度，滑雪的路径必须向下倾斜，每次可以向上下左右4个方向滑行。区域