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

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:

  Programming, Dynamics, Dynamic programming

Information

Related search queries