动态规划1.ppt

动态规划初步
常州市第一中学吴争锴
最长不下降子序列(LIS)
问题描述:
给定一个整数序列,求出长度最长的子序列,使得该序列中的元素严格不降。
最长不下降子序列
经典做法:
O(n^2):f[i]=max(f[j]|j<I && a[j]<=a[i])
如何优化?
最长不下降子序列
O(nlogn):注意到如果记所有长度为k的不下降子序列中最后一个数最小的为p[k],则p[k]单调不降。那么每次决策时选择max(p[k]|p[k]<=a[i]),则f[i]=k+1。再用a[i]更新p[k+1],容易证明该算法正确性。
算法复杂度为O(nlogn)。
例题
导弹拦截:Dilworth定理
JSOI省队训练NOI2009\Heap
最长公共子串(LCS)
给定两个字符串S1,S2,求出一个最长的字符串S使得其同时是S1、S2的子串。
最长公共子串
经典做法
O(n^2):f[i][j]=f[i-1][j-1]+1 if s1[i]==s2[j]
0 otherwise
能否拓展到多串?
多维状态,复杂度过高?
有其他做法?枚举答案串在第一个串中的开始位置,然后使用KMP算法。
能否优化?
最长公共子串
实际上从动态规划的角度复杂度已经难以再优化了。
然而使用后缀数组可以做到O(LlogL)的复杂度,其中L为字符串总长度。
有兴趣的同学可以课后研究。
最长公共子串
扩展:
一类字符串匹配DP题:
ALIGN顺序对齐
背包问题
背包:给定若干个物品,每个物品有价值和体积,要求选出一个物品的子集,使得在其体积总和不超过给定大小的情况下价值总和最大。
有限背包:每个物品只能取有限次。
无限背包:每个物品能取任意次
部分背包:每个物品不一定取整数个