Transcription of Dynamic Programming - Stanford University
{{id}} {{{paragraph}}}
Example: barber
Dynamic Programming - Stanford University
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: 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!
Tree DP Example Problem: given a tree, color nodes black as many as possible without coloring two adjacent nodes Subproblems: – First, we arbitrarily decide the root node r – B v: the optimal solution for a subtree having v as the root, where we color v black – W v: the optimal solution for a subtree having v as the root, where we don’t color v – Answer is max{B
Loading..
Tags:
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: