综合练习:如何查资料、整理资料 Lecture 3. Dynamic ■资料来源 Programming ■资料使用 清华大学宋斌 Dynamic programming 动态规划方法回顾 a Longest common subsequence ■与分治方法有没有共同点?【不同点】 ■ Printing neatly 子问题空间?决定复杂性因子之 子问题的治与合?复杂性因子之二 最优值 ■技巧: Memoization备忘录法 ■最优解 讨论] 最长公共子序列 问题定义 m A finite alphabet a finite set R of strings from A', and f Awith w I>= K such that w each x element of r? -complete for alA(R)>=21 清华大学 宋斌恒 1 Lecture 3. Dynamic Programming 清华大学 宋斌恒 清华大学 宋斌恒 2 综合练习：如何查资料、整理资料 n 资料来源 n 资料整理 n 资料使用 清华大学 宋斌恒 3 Dynamic programming n Longest common subsequence n Printing neatly n Edit distance n Optimal binary search tree n 技巧：Memoization[备忘录法] 清华大学 宋斌恒 4 动态规划方法回顾 n 与分治方法有没有共同点？【不同点】 n 子问题空间？决定复杂性因子之一 n 子问题的治与合？复杂性因子之二 n 最优值 n 最优解 n [讨论] 清华大学 宋斌恒 5 最长公共子序列 清华大学 宋斌恒 6 问题定义 n Given : n A finite alphabet A, finite set R of strings from A*, and apositiveinteger K n Is There : n A string w element of A* with | w | >= K such that w is a subsequence of each x element of R ? n The problem remains NP-complete for all A ( R ) >= 2 n Analogous Longest Common Substring problem is trivially solvable in polynomial time