Dynamic Programming
Dr. Dwiti Krishna Bebarta
Text Books:
1. Ellis Horowitz, SartajSahni, Sanguthevar Rajasekaran, “Fundamentals of
Computer Algorithms”, 2nd Edition, Universities Press.
2. Introduction to Algorithms Thomas H. Cormen, PHI Learning
Contents
• The general method
• Multistage Graphs
• All pairs-shortest paths
• Optimal Binary search trees
• 0/1 Knapsack Problem
• The traveling salesperson problem
The General Method
What is Dynamic Programming?
• Dynamic programming solves optimization problems by
combining solutions to sub-problems
• “Programming” refers to a tabular method with a series of
choices.
• A set of choices must be made to arrive at an optimal
solution
• As choices are made, sub-problems of the same form arise
frequently
• The key is to store the solutions of sub-problems to be
reused in the future
Example 1
• Fibonacci numbers are defined by:
F0 0
F1 1
Fi Fi 1 Fi 2 for i 2.
Time Complexity?
Fibonacci Example
Waste time redoing work
Time:
Exponential
Memorization in Optimization
• Definition: An algorithmic technique which saves
(memorizes) a computed answer for later reuse, rather than
re-computing the answer.
• Remember the solutions for the sub-instances
• If the same sub-instance needs to be solved again, the same
answer can be used.
Memorization
From Memoization to Dynamic Programming
• Determine the set of subinstances that need to be
solved.
• Instead of recursing from top to bottom, solve each of
the required subinstances in smallest to largest order,
storing results along the way.
Dynamic Programming
First determine the complete set of subinstances
{100, 99, 98,…, 0}
Compute them in an order
Smallest to largest
such that no friend must wait.
1
0 9
Dynamic Programming vs Divide-and-Conquer
• Recall the divide-and-conquer approach
– Partition the problem into independent subproblems
– Solve the subproblems recursively
– Combine solutions of subproblems
– e.g., mergesort, quicksort
• This contrasts with the dynamic programming
approach
Dynamic Programming vs Divide-and-Conquer
• Dynamic programming is applicable when sub-problems
are not independent
– i.e., sub-problems share sub-sub-problems
– Solve every sub-sub-problem only once and store the
answer for use when it reappears
A dynamic programming approach consists of a sequence of
4 steps
1. Characterize the structure of an optimal solution
2. Recursively define the value of an optimal solution
3. Compute the value of an optimal solution in a bottom-
up fashion
4. Construct an optimal solution from computed
information (Optional)
