6.006 20. Dynamic programming II: Longest common subsequence

MIT OpenCourseWare http://ocw.mit.edu6.006Introduction to AlgorithmsSpring 2008For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms. � � � Lecture 20 Dynamic Programming II of IV 6.006 Spring 2008Lecture 20: Dynamic Programming II: LongestCommon Subsequence, Parent PointersLecture Overview • Review of big ideas & examples so far • Bottom-up implementation • Longest common subsequence • Parent pointers for guesses Readings CLRS 15 Summary * DP ≈ “controlled brute force” * DP ≈ guessing + recursion + memoization * DP ≈ dividing into reasonable � subproblems whose solutions relate -acyclicly -usually via guessing parts of solution. * time = � subproblems × time/subproblemtreating recursive calls as O(1) (usually mainly guessing) • essentially an amortization • count each subproblem only once; after first time, costs O(1) via memoization 1Lecture 20 Dynamic Programming II of IV 6.006 Spring 2008Examples: Fibonacci Shortest Paths Crazy Eightssubprobs: fib(k) δk(s, t)∀s,k < n trick(i) = longest 0 ≤ k ≤ n = min path s → t trick from card(i) using ≤ k edges � subprobs: Θ(n) Θ(V 2) Θ(n) guessing: none edge from s, if any next card j � choices: 1 deg(s) n − i relation: = fib(k − 1) =min{δk−1(s, t)} = 1 + max(trick(j)) + fib(k − 2) u{w(s, v)+ δk−1(v, t) for ic[i, j + 1]: c[i, j]= c[i +1,j] parent[i, j]=(i +1,j) else: c[i, j]= c[i, j + 1] parent[i, j]=(i, j + 1) . . . and follow them at the end: • lcs = [ ] here = (0,0) while c[here]: if x[i] == y[j]: lcs.append(x[i]) here = parent[here] 5