Dynamic Programming - Stanford University

← Back to document page

Dynamic ProgrammingJaehyun ParkCS 97SIStanford UniversityJune 29, 2015OutlineDynamic Programming1-dimensional DP2-dimensional DPInterval DPTree DPSubset DPDynamic Programming2What 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 Programming3Steps for Solving DP down the recurrence that relates and solve the base cases Each step is very important! Dynamic Programming4OutlineDynamic 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 +

Dynamic Programming 3. Steps for Solving DP Problems 1. Define subproblems 2. Write down the recurrence that relates subproblems 3. Recognize and solve the base cases ... – Let D n be the number of ways to write n as the sum of 1, 3, 4

  Programming, Dynamics, Dynamic programming