Dynamic
Programming
A Key Technique in Algorithm Design
OUR
Anas TEAM Kashif
Khan Nazir
Sheraz Naima
Mirza Shoukat
Introduction to Dynamic
Programming
• Dynamic Programming (DP) is a
method for solving complex
problems by breaking them into
simpler subproblems.
• It is used when subproblems
repeat (overlapping
subproblems).
• Solves problems efficiently by
storing previous results
(memoization).
Key Characteristics of DP
Optimal Overlapping Memoization or
Substructure: Subproblems: Tabulation:
Solution to a problem Same subproblems are Techniques to store and
can be built from solved multiple times. reuse computed
solutions to results.
subproblems.
DP vs Divide &
Conquer
Dynamic Divide &
Programming (DP): Conquer:
● Solves overlapping subproblems. ● Solves subproblems
independently.
● Stores results to avoid
recomputation. ● Does not store results of
subproblems.
● Efficient for problems with
repeated substructures (e.g., ● Works best when subproblems
Fibonacci). don’t overlap (e.g., Merge Sort).
DP
Approaches General
y
Bottom-Up is
generally
more space-
efficient.
Bottom- Top-
Up Down:
Iterative + Recursive +
Tabulation. Memoization.
Common DP Problems
Longest Common
Subsequence (LCS)
Fibonacci
Numbers
0/1 Knapsack
Problem
Matrix Chain
Multiplication
Coin Change
Problem
Example – Fibonacci with DP
Naive O(2ⁿ), repeats subproblems
Recursive
With
O(n), stores computed values
Memoization
Shows clear benefit of DP in
benefit
reducing time complexity.
0/1 Knapsack – DP
Solution
Objectiv
e table format
Maximize profit Use a table to build
under weight solutions step-by-
constraint step.
Time
Complexity
O(n * W), where W
is capacity.
When to Use DP
Problem can be broken
into subproblems.
Subproblems
repeat.
Problem has optimal
substructure.
You need efficient solutions to
exponential brute-force approaches.
Real-Life Applications
Game AI
(shortest paths, Route
score optimization
maximization (Google Maps)
Spell checkers Data
(edit distance) compression
algorithms
THANKS
FOR
WATCHI
NG
