18-12-2012, 02:07 PM
Dynamic Programming and Greedy Method
Dynamic Programming.pdf (Size: 693.9 KB / Downloads: 159)
Elements of Dynamic Programming
• Optimal sub-structure (Principle of Optimality)
– an optimal solution to the problem contains within it optimal
solutions to sub-problems.
• Overlapping subproblems
– there exist some places where we solve the same subproblem
more than once
Steps to Designing a
Dynamic Programming Algorithm
1. Characterize optimal sub-structure
2. Recursively define the value of an optimal solution
3. Compute the value bottom up
4. (if needed) Construct an optimal solution
Recap: Elements of Dynamic Programming
Optimal substructure (Principle of Optimality)
– Example. In MCM, A1..6 = A1..3 A4..6
• Overlapping subproblems
– there exist some places where we solve the same
subproblem more than once
– Example. In MCM, A2..3 is common to the subproblems
A1..3 and A2..4
– Effort wasted in solving common sub-problems
repeatedly
Memoization
• Memoization is one way to deal with overlapping
subproblems
– After computing the solution to a subproblem,
store it in a table
– Subsequent calls just do a table lookup
• Can modify recursive algo to use memoziation