动态规划算法整理ppt.ppt

Chapter 7 动态规划Dynamic Programming What is dynamic programming 与分治法类似, 动态规划也是通过组合子问题的解来求解问题. 分治算法将问题划分成独立子问题, 递归地解决这些子问题, 然后组合这些子问题的解来求解原始问题. If these subproblems are not independent, what will happen? 算法总体思想 Fibonacci sequence(序列) Fibonacci序列定义如下： 1. procedure f(n) 2. if n=1 or n=2 then return 1 3. else return f(n-1)+f(n-2) 这种递归形式有简洁、容易书写和容易查错等优点, 最主要是它的抽象性. 但是它远不是有效的算法. 算法复杂性: ?(?n) Why??? Fibonacci sequence分析 f(n)= f(n-1)+ f(n-2) =2f(n-2)+ f(n-3) =3f(n-3)+2f(n-4) =5f(n-4)+3f(n-5) 二项式系数的计算 What is dynamic programming什么是动态规划？ 当子问题发生重叠时, 分治法做了很多不必要的工作——重复对重叠的子问题进行求解. 动态规划算法对每个子问题求解一次, 然后将结果保存在一张表里面, 这样可以避免每个已求解子问题的重复计算. 对于Fibonacci序列, 一个明显的方法是从f(1)开始自底向上地计算到f(n), 只需要?(n)时间和?(1)空间. 和前面的方法相比, 可以很大程度降低时间复杂度. The longest common subsequence problem最长公共子序列问题 在字母表?上, 分别给出两个长度为n和m的字符串A和B, 确定在A和B中最长公共子序列的长度. 这里A=a1a2...an的子序列的一个形式为ai1ai2...aik的字符串, 其中每个ij在1到n之间, 并且1?i1i2...ik?n 蛮力法: 列举A所以的2n个子序列, 对于每一子序列在?(m)时间内来确定它是否也是B的子序列. 很明显, 此算法的时间复杂的为?(m*2n). 递推公式 为了使用动态规划技术, 首先推导一个求最长公共子序列长度的递推公式. 令A=a1a2...an和B=b1b2...bm 令L[i, j]表示a1a2...ai和b1b2...bj的最长公共子序列的长度(i, j可能是0, 此时a1a2...ai和b1b2...bj中至少一个为空). 可得如下结论： 递推公式 观察结论7.1 如果i和j都大于0, 那么 若ai=bj, L[i, j]=L[i-1, j-1]+1 若ai?bj, L[i, j]=max{L[i, j-1], + L[i-1, j]} 可得如下公式： 现在可以直接用动态规划技术来求解最长公共子序列问题。对每一对i和j的值，0 ? i ? n，0 ? j ? m，我们用一个(n+1)×(m+1)表来计算L[i, j]的值，只需要用上面的公式逐行地填表L[0…n, 0…m]。算法如下： Algorithm 7.1 LCS Input: Two strings A and B of length n and m, respectively, over an alphabet ? Output: The length of the longest common subsequence of A and B 1. for i?0 to n 2. L[i, 0]?0 3. end for 4. for j?0 to m 5. L[0, j]?0 6. end for 7. for i?1 to n 8. for j?1 to m 9. if ai=bj then L[i, j]?L[i-1, j-1]+1 10. else L[i, j]?max{L[i, j-1], L[i-1, j]} 11. end if 12. end for 13. end for 14. return L[n, m] 定理7.1 最长公共子序列问题的最优解能够在?(nm)时间和?(min{m, n}) 空间内得到. ？ A=“xyxxzxyzxy” B=“zxzyyzxxyxxz” Algorithm 7.1pro LCS 1. for i