Dynamic Programming - Stanford University

1 Dynamic ProgrammingJaehyun ParkCS 97 SIStanford UniversityJune 29, 2015 OutlineDynamic Programming1-dimensional DP2-dimensional DPInterval DPTree DPSubset DPDynamic Programming2 What is DP? Wikipedia definition: method for solving complex problemsby breaking them down into simpler subproblems This definition will make sense once we see some examples Actually, we ll only see problem solving examples todayDynamic Programming3 Steps for Solving DP down the recurrence that relates and solve the base cases Each step is very important! Dynamic Programming4 OutlineDynamic Programming1-dimensional DP2-dimensional DPInterval DPTree DPSubset DP1-dimensional DP51-dimensional DP Example Problem: givenn, find the number of different ways to writenas the sum of 1, 3, 4 Example.

2 Forn= 5, the answer is 65 = 1 + 1 + 1 + 1 + 1= 1 + 1 + 3= 1 + 3 + 1= 3 + 1 + 1= 1 + 4= 4 + 11-dimensional DP61-dimensional DP Example Define subproblems LetDnbe the number of ways to writenas the sum of 1, 3, 4 Find the recurrence Consider one possible solutionn=x1+x2+ +xm Ifxm= 1, the rest of the terms must sum ton 1 Thus, the number of sums that end withxm= 1is equal toDn 1 Take other cases into account (xm= 3,xm= 4)1-dimensional DP71-dimensional DP Example Recurrence is thenDn=Dn 1+Dn 3+Dn 4 Solve the base cases D0= 1 Dn= 0for all negativen Alternatively, can set:D0=D1=D2= 1, andD3= 2 We re basically done!1-dimensional DP8 ImplementationD[0] = D[1] = D[2] = 1; D[3] = 2;for(i = 4; i <= n; i++)D[i] = D[i-1] + D[i-3] + D[i-4]; Very short!

3 Extension: solving this for hugen, sayn 1012 Recall the matrix form of Fibonacci numbers1-dimensional DP9 POJ 2663: Tri Tiling Givenn, find the number of ways to fill a3 nboard withdominoes Here is one possible solution forn= 121-dimensional DP10 POJ 2663: Tri Tiling Define subproblems DefineDnas the number of ways to tile a3 nboard Find recurrence DP11 Troll Tiling1-dimensional DP12 Defining Subproblems Obviously, the previous definition didn t work very well Dn s don t relate in simple terms What if we introduce more subproblems?1-dimensional DP13 Defining Subproblems1-dimensional DP14 Finding Recurrences1-dimensional DP15 Finding Recurrences Consider different ways to fill thenth column And see what the remaining shape is Exercise: Finding recurrences forAn,Bn,Cn Just for fun, why isBnandEnalways zero?

4 Extension: solving the problem forn mgrids, wherenissmall, sayn 10 How many subproblems should we consider?1-dimensional DP16 OutlineDynamic Programming1-dimensional DP2-dimensional DPInterval DPTree DPSubset DP2-dimensional DP172-dimensional DP Example Problem: given two stringsxandy, find the longest commonsubsequence (LCS) and print its length Example: x:ABCBDAB y:BDCABC BCAB is the longest subsequence found in both sequences, sothe answer is 42-dimensional DP18 Solving the LCS Problem Define subproblems LetDijbe the length of the LCS Find the recurrence Ifxi=yj, they both contribute to the LCS Dij=Di 1,j 1+ 1 Otherwise, eitherxioryjdoes not contribute to the LCS, soone can be dropped Dij= max{Di 1,j, Di,j 1} Find and solve the base cases:Di0=D0j= 02-dimensional DP19 Implementationfor(i = 0; i <= n.)

5 I++) D[i][0] = 0;for(j = 0; j <= m; j++) D[0][j] = 0;for(i = 1; i <= n; i++) {for(j = 1; j <= m; j++) {if(x[i] == y[j])D[i][j] = D[i-1][j-1] + 1;elseD[i][j] = max(D[i-1][j], D[i][j-1]);}}2-dimensional DP20 OutlineDynamic Programming1-dimensional DP2-dimensional DPInterval DPTree DPSubset DPInterval DP21 Interval DP Example Problem: given a stringx= , find the minimum numberof characters that need to be inserted to make it a palindrome Example: x:Ab3bd Can get dAb3bAd or Adb3bdA by inserting 2 characters(one d , one A )Interval DP22 Interval DP Example Define subproblems LetDijbe the minimum number of characters that need to beinserted to a palindrome Find the recurrence Consider a shortest Eithery1=xioryk=xj(why?

6 1is then an optimal solution forxi+ 1orxi+ 1 Last case possible only ify1=yk=xi=xjInterval DP23 Interval DP Example Find the recurrenceDij={1 + min{Di+1,j, Di,j 1}xi6=xjDi+1,j 1xi=xj Find and solve the base cases:Dii=Di,i 1= 0for alli The entries ofDmust be filled in increasing order ofj iInterval DP24 Interval DP Example// fill in base cases herefor(t = 2; t <= n; t++)for(i = 1, j = t; j <= n; i++, j++)// fill in D[i][j] here Note how we use an additional variabletto fill the table incorrect order And yes, for loops can work with multiple variablesInterval DP25An Alternate Solution Reversexto getxR The answer isn L, whereLis the length of the LCS ofxandxR Exercise: Think about why this worksInterval DP26 OutlineDynamic Programming1-dimensional DP2-dimensional DPInterval DPTree DPSubset DPTree DP27 Tree DP Example Problem: given a tree, color nodes black as many as possiblewithout coloring two adjacent nodes Subproblems: First, we arbitrarily decide the root noder Bv: the optimal solution for a subtree havingvas the root,where we colorvblack Wv.}

7 The optimal solution for a subtree havingvas the root,where we don t colorv Answer ismax{Br, Wr}Tree DP28 Tree DP Example Find the recurrence Crucial observation: oncev s color is determined, subtrees canbe solved independently Ifvis colored, its children must not be coloredBv= 1 + u children(v)Wu Ifvis not colored, its children can have any colorWv= 1 + u children(v)max{Bu, Wu} Base cases: leaf nodesTree DP29 OutlineDynamic Programming1-dimensional DP2-dimensional DPInterval DPTree DPSubset DPSubset DP30 Subset DP Example Problem: given a weighted graph withnnodes, find theshortest path that visits every node exactly once (TravelingSalesman Problem) Wait, isn t this an NP-hard problem? Yes, but we can solve it inO(n22n)time Note: brute force algorithm takesO(n!)

8 TimeSubset DP31 Subset DP Example Define subproblems DS,v: the length of the optimal path that visits every node inthe setSexactly once and ends atv There are approximatelyn2nsubproblems Answer isminv VDV,v, whereVis the given set of nodes Let s solve the base cases first For each nodev,D{v},v= 0 Subset DP32 Subset DP Example Find the recurrence Consider a path that visits all nodes inSexactly once andends atv Right before arrivingv, the path comes from someuinS {v} And that subpath has to be the optimal one that coversS {v}, ending atu We just try all possible candidates foruDS,v= minu S {v}(DS {v},u+ cost(u, v))Subset DP33 Working with Subsets When working with subsets, it s good to have a nicerepresentation of sets Idea.

9 Use an integer to represent a set Concise representation of subsets of small integers{0,1, ..} If theith (least significant) digit is 1,iis in the set If theith digit is 0,iis not in the set ,19 =010011(2)in binary represent a set{0,1,4}Subset DP34 Using Bitmasks Union of two setsxandy:x | y Intersection:x & y Symmetric difference:x y Singleton set{i}:1 << i Membership test:x & (1 << i) != 0 Subset DP35 Conclusion Wikipedia definition: a method for solving complex problemsby breaking them down into simpler subproblems Does this make sense now? Remember the three steps! the base casesSubset DP36