PPT: Dynamic Programming | Algorithms - Computer Science Engineering (CSE) PDF Download

 Page 1


Dynamic 
Programming
Page 2


Dynamic 
Programming
Introduction
Definition
A method for solving complex problems by breaking them into overlapping subproblems, solving each 
subproblem once, and storing results for reuse.
Key Properties
Optimal Substructure: Optimal solution to the problem contains optimal solutions to subproblems.
Overlapping Subproblems: Subproblems recur multiple times during computation.
Approaches
Top-Down (Memoization): Recursive, store results in a lookup table.
Bottom-Up (Tabulation): Iterative, build solution from smaller subproblems.
Page 3


Dynamic 
Programming
Introduction
Definition
A method for solving complex problems by breaking them into overlapping subproblems, solving each 
subproblem once, and storing results for reuse.
Key Properties
Optimal Substructure: Optimal solution to the problem contains optimal solutions to subproblems.
Overlapping Subproblems: Subproblems recur multiple times during computation.
Approaches
Top-Down (Memoization): Recursive, store results in a lookup table.
Bottom-Up (Tabulation): Iterative, build solution from smaller subproblems.
Principle of Optimality
Definition
An optimal solution to a problem can be constructed 
from optimal solutions to its subproblems.
The key idea is to break problems into smaller 
subproblems, solve each optimally, and combine 
solutions.
Example
Shortest path from A to D: Optimal path A³B³C³D 
includes optimal subpaths (e.g., A³B, B³C).
Conditions for DP
Problem has optimal substructure
Subproblems overlap (same subproblems solved 
multiple times)
Page 4


Dynamic 
Programming
Introduction
Definition
A method for solving complex problems by breaking them into overlapping subproblems, solving each 
subproblem once, and storing results for reuse.
Key Properties
Optimal Substructure: Optimal solution to the problem contains optimal solutions to subproblems.
Overlapping Subproblems: Subproblems recur multiple times during computation.
Approaches
Top-Down (Memoization): Recursive, store results in a lookup table.
Bottom-Up (Tabulation): Iterative, build solution from smaller subproblems.
Principle of Optimality
Definition
An optimal solution to a problem can be constructed 
from optimal solutions to its subproblems.
The key idea is to break problems into smaller 
subproblems, solve each optimally, and combine 
solutions.
Example
Shortest path from A to D: Optimal path A³B³C³D 
includes optimal subpaths (e.g., A³B, B³C).
Conditions for DP
Problem has optimal substructure
Subproblems overlap (same subproblems solved 
multiple times)
Overlapping Subproblems
Definition
Subproblems are 
solved repeatedly in 
a recursive solution, 
leading to 
redundant 
computations.
Solution
Store results of 
subproblems to 
avoid 
recomputation. Use 
a table (array) for 
tabulation or a 
cache for 
memoization.
Time Savings
Naive recursion: 
O(2^n) for Fibonacci. 
DP: O(n) with 
memoization or 
tabulation.
Page 5


Dynamic 
Programming
Introduction
Definition
A method for solving complex problems by breaking them into overlapping subproblems, solving each 
subproblem once, and storing results for reuse.
Key Properties
Optimal Substructure: Optimal solution to the problem contains optimal solutions to subproblems.
Overlapping Subproblems: Subproblems recur multiple times during computation.
Approaches
Top-Down (Memoization): Recursive, store results in a lookup table.
Bottom-Up (Tabulation): Iterative, build solution from smaller subproblems.
Principle of Optimality
Definition
An optimal solution to a problem can be constructed 
from optimal solutions to its subproblems.
The key idea is to break problems into smaller 
subproblems, solve each optimally, and combine 
solutions.
Example
Shortest path from A to D: Optimal path A³B³C³D 
includes optimal subpaths (e.g., A³B, B³C).
Conditions for DP
Problem has optimal substructure
Subproblems overlap (same subproblems solved 
multiple times)
Overlapping Subproblems
Definition
Subproblems are 
solved repeatedly in 
a recursive solution, 
leading to 
redundant 
computations.
Solution
Store results of 
subproblems to 
avoid 
recomputation. Use 
a table (array) for 
tabulation or a 
cache for 
memoization.
Time Savings
Naive recursion: 
O(2^n) for Fibonacci. 
DP: O(n) with 
memoization or 
tabulation.
Memoization vs. Tabulation
Memoization (Top-Down)
Recursive approach with a cache to store results. 
Solves only required subproblems. Intuitive and uses 
lazy evaluation, but has recursive overhead and 
stack space concerns.
Tabulation (Bottom-Up)
Iterative approach, building table from smallest 
subproblems. Solves all subproblems systematically. 
No recursion and efficient, but may solve 
unnecessary subproblems.
Both approaches typically have O(n) or O(n²) time complexity and O(n) or O(n²) space complexity. Choose based on 
problem structure and implementation ease.