6.006 19. Dynamic programming I: Memoization, Fibonacci, Crazy Eigh

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 19 Dynamic Programming I of IV 6.006 Spring 2008Lecture 19: Dynamic Programming I:Memoization, Fibonacci, Crazy Eights, GuessingLecture Overview • Fibonacci Warmup • Memoization and subproblemsShortest Paths• • Crazy Eights • Guessing Viewpoint Readings CLRS 15 Dynamic Programming (DP) Big idea: :hard yet simple • Powerful algorithmic design technique • Large class of seemingly exponential problems have a polynomial solution (“only”) via DP • Particularly for optimization problems (min /max) (e.g., shortest paths) * DP ≈ “controlled brute force” * DP ≈ recursion + re-use Fibonacci Numbers F1 = F2 = 1; Fn = Fn−1 + Fn−2 Naive Algorithm follow recursive definition fib(n): if n ≤ 2: return 1 else return fib(n − 1) + fib(n − 2) = ⇒ T (n)= T (n − 1) + T (n − 2) + O(1) ≈ φn ≥ 2T (n − 2) + O(1) ≥ 2n/2 EXPONENTIAL -BAD! 1 � � � Lecture 19 Dynamic Programming I of IV 6.006 Spring 2008FnFn-1Fn-2Fn-2Fn-3Fn-3Fn-4Figure 1: Naive Fibonacci Algorithm Simple Idea memoize memo = {} fib(n): if n in memo: return memo[n] else: if n ≤ 2: f =1 else: f = fib(n − 1) + fib(n − 2) free memo[n]= f return f T (n)= T (n − 1) + O(1) = O(n) [Side Note: There is also an O(lg n)-time algorithm for Fibonacci, via different techniques] * DP ≈ recursion + memoization • remember (memoize) previously solved “subproblems” that make up problem – in Fibonacci, subproblems are F0,F1, ,Fn··· • if subproblem already solved, re-use solution * = time = � of subproblems time/subproblem⇒ · • – in fib: � of subproblems is O(n) and time/subproblem is O(1) -giving us a total time of O(n). 2 ������� �� � �Lecture 19 Dynamic Programming I of IV 6.006 Spring 2008Shortest PathsRecursive formulation: • δ(s, t) = min{w(s, v)+ δ(v, t)(s, v) �E}does this work with memoization? • no, cycles = infinite loops (see Figure 2). ⇒ tsFigure 2: Shortest Paths • in some sense necessary for neg-weight cycles • works for directed acyclic graphs in O(V + E) (recursion effectively DFS/topological sort) • trick for shortest paths: removing cyclic dependency. – δk(s, t) = shortest path using ≤ k edges = min{δk−1(s, t)}∪{w(s, v)+ δk−1(v, t) (s, v) �E}timesubproblemstime/subproblem�= � . . . except δk(t, t)= φ, δφ(s, t)= ∞ if s =�t – δ(s, t)= δn−1(s, t) assuming no negative cycles =⇒·for3) s,t,k�··· = O(V deg(V )) = O(VE)· V * Subproblem dependency should be acyclic. really O(n2) O(n)really degV···O(n 3• � � � Lecture 19 Dynamic Programming I of IV 6.006 Spring 2008Crazy Eights Puzzle • given a sequence of cards c[φ],c[1], ··· ,c[n − 1]e.g., 7♥, 6♥, 7♦, 3♦, 8♣,J♠• find longest left-to-right “trick” (subsequence) c[i1],c[i2],c[ik](i1 i) = time = � subproblems time/subproblem⇒ � � � · � � � O(n) O(n) = O(n2) (to find actual trick, trace through max’s) “Guessing” Viewpoint • what is the first card in best trick? guess!i.e., try all possibilities & take best result-only O(n) choices• what is next card in best trick from i? guess! – if you pretend you knew, solution becomes easy (using other subproblems) – actually pay factor of O(n) to try all * use only small � choices/guesses per subproblem poly(n)∼O(1) 4