Dynamic Programming: Overlapping Subproblems, Memoization vs Tabulation0%
Classic DP Master Patterns: 0/1 Knapsack, Coin Change & LCS

Dynamic Programming: Overlapping Subproblems, Memoization vs Tabulation

Beginner12 min read•Updated: Jul 11, 2026
Study MaterialsCheatsheet

Dynamic Programming: Overlapping Subproblems, Memoization vs Tabulation

Dynamic Programming (DP) is a powerful algorithmic paradigm used to solve complex optimization problems by breaking them down into simpler, overlapping subproblems. Rather than recomputing solutions to identical subproblems repeatedly, DP computes each subproblem solution exactly once and stores the result in memory (caching).

Dynamic Programming Overlapping Subproblems and MemoizationClick to Zoom
Dynamic Programming Overlapping Subproblems and Memoization

1. The Two Core Prerequisites of DP

A problem can be solved with Dynamic Programming if and only if it exhibits both of the following mathematical properties:

  1. 1
    Optimal Substructure:
  • An optimal solution to the overall problem contains within it optimal solutions to its subproblems.
  • Example: The shortest path from $A$ to $C$ via $B$ consists of the shortest path from $A$ to $B$ plus the shortest path from $B$ to $C$.
  1. 1
    Overlapping Subproblems:
  • The recursive decomposition visits the same identical subproblem states repeatedly.
  • Example: In naive Fibonacci calculation:

$$\text{Fib}(5) = \text{Fib}(4) + \text{Fib}(3)$$ $$\text{Fib}(4) = \text{Fib}(3) + \text{Fib}(2)$$ Notice that $\text{Fib}(3)$ is computed twice, $\text{Fib}(2)$ three times, leading to explosive $O(2^n)$ exponential duplication!

2. Top-Down Memoization vs. Bottom-Up Tabulation

Output
Problem Decomposition Approaches
|
+-----------------------+-----------------------+
| |
Top-Down (Memoization) Bottom-Up (Tabulation)
- Recursive with caching - Iterative table building
- Starts at target state (N) - Starts at base cases (0, 1)
- Solves only required subproblems - Solves all subproblems in order
- Incurs call stack overhead - Eliminates recursion stack (O(1) space optimization possible)

Direct Comparison

FeatureTop-Down (Memoization)Bottom-Up (Tabulation)
Flow of ExecutionRoot to Leaves (Target down to Base Cases)Leaves to Root (Base Cases up to Target)
ImplementationRecursion + Cache (Hash Map or Array)Iterative for loops + Array table
Subproblem CoverageComputes only reachable subproblemsComputes all table states in sequence
Space OptimizationDifficult to reduce space complexityOften reducible from $O(n)$ to $O(1)$ space
Stack Overflow RiskYes, if recursion depth exceeds system limitZero risk; pure iterative execution

3. The 5-Step Framework to Master Any DP Problem

When faced with any DP question in an interview, follow this structured blueprint:

  1. 1
    Define the State: What does dp[i] (or dp[i][j]) represent in plain English?
  2. 2
    Formulate the Recurrence Relation (Transition): How does dp[i] depend on previous states (e.g., dp[i-1], dp[i-2])?
  3. 3
    Identify the Base Cases: What are the trivial stopping conditions that cannot be broken down further (e.g., dp[0] = 0, dp[1] = 1)?
  4. 4
    Determine the Order of Computation: In what order must the table be filled so that dependencies are already resolved when calculating the current state?
  5. 5
    Space Optimization (Optional): Can we replace the full $O(n)$ array with just 2 or 3 scalar variables?

4. Case Study: Climbing Stairs (LeetCode 70)

Problem: You are climbing a staircase with $n$ steps. Each time you can climb either 1 or 2 steps. In how many distinct ways can you climb to the top?

Step 1: State Definition

Let dp[i] be the number of distinct ways to reach step i.

Step 2: Recurrence Relation

To reach step i, you could have jumped from step i-1 (by taking 1 step) or from step i-2 (by taking 2 steps): $$\text{dp}[i] = \text{dp}[i-1] + \text{dp}[i-2]$$

Step 3: Base Cases

  • dp[1] = 1 (Only 1 way: [1])
  • dp[2] = 2 (2 ways: [1, 1] or [2])

Step-by-Step Trace Table for $n = 5$

Step ($i$)Ways from $i-1$Ways from $i-2$Total Ways dp[i]Possible Paths
1--1(1)
2--2(1+1), (2)
3dp[2] = 2dp[1] = 13(1+1+1), (2+1), (1+2)
4dp[3] = 3dp[2] = 25All 3 from step 3 + all 2 from step 2
5dp[4] = 5dp[3] = 38$5 + 3 = 8$ distinct paths

5. Dual-Language Implementation

Python 3: All Approaches

Python
from typing import Dict
 
# 1. Top-Down Memoization (Recursive)
def climb_stairs_memo(n: int) -> int:
memo: Dict[int, int] = {1: 1, 2: 2}
 
def dp(step: int) -> int:
if step in memo:
return memo[step]
memo[step] = dp(step - 1) + dp(step - 2)
return memo[step]
 
return dp(n)
 
# 2. Bottom-Up Tabulation (Iterative O(N) Space)
def climb_stairs_tabulation(n: int) -> int:
if n <= 2:
return n
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
 
# 3. Space-Optimized Bottom-Up (O(1) Auxiliary Space)
def climb_stairs_optimized(n: int) -> int:
if n <= 2:
return n
prev2, prev1 = 1, 2
for _ in range(3, n + 1):
current = prev1 + prev2
prev2 = prev1
prev1 = current
return prev1
 
# Example Test
if __name__ == "__main__":
print("Ways for 5 stairs (Memo):", climb_stairs_memo(5)) # 8
print("Ways for 5 stairs (Tab):", climb_stairs_tabulation(5)) # 8
print("Ways for 5 stairs (Opt):", climb_stairs_optimized(5)) # 8

Modern JavaScript (Node.js) Implementation

JavaScript
// 1. Top-Down Memoization
function climbStairsMemo(n, memo = new Map([[1, 1], [2, 2]])) {
if (memo.has(n)) return memo.get(n);
const result = climbStairsMemo(n - 1, memo) + climbStairsMemo(n - 2, memo);
memo.set(n, result);
return result;
}
 
// 2. Space-Optimized Bottom-Up Tabulation (O(1) Space)
function climbStairsOptimized(n) {
if (n <= 2) return n;
let prev2 = 1;
let prev1 = 2;
 
for (let i = 3; i <= n; i++) {
const current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
 
return prev1;
}
 
// Example Test
console.log("Climb Stairs (5) Memo:", climbStairsMemo(5)); // 8
console.log("Climb Stairs (5) Opt:", climbStairsOptimized(5)); // 8

6. Complexity Comparison

ImplementationTime ComplexityAuxiliary Space ComplexityCall Stack Overhead
Naive Recursion$O(2^n)$ (Exponential!)$O(n)$Yes
Top-Down Memoization$O(n)$ (Linear)$O(n)$ (Memo table + Call stack)Yes
Bottom-Up Tabulation$O(n)$ (Linear)$O(n)$ (DP array)No
Space-Optimized DP$O(n)$ (Linear)$O(1)$ (Only two variables)No
Interactive Quiz

Multiple Choice Questions

Question 1
Which two conditions must a problem satisfy to be solvable with Dynamic Programming?
Question 2
What is the fundamental difference between Memoization and Tabulation?
Question 3
How does Dynamic Programming reduce the time complexity of the Fibonacci calculation from naive recursion $O(2^n)$ to $O(n)$?
Question 4
When is space optimization from $O(n)$ down to $O(1)$ achievable in a 1D Dynamic Programming problem?
Question 5
What risk is inherent to Top-Down Memoization that is completely eliminated by Bottom-Up Tabulation?
Next Lesson

Classic DP Master Patterns: 0/1 Knapsack, Coin Change & LCS

Continue learning with hands-on practice, examples, and exercises in the upcoming topic.

Related Lessons

Previous LessonNext Lesson
Shortest Paths: Dijkstra's Algorithm with Min-Heap & BFS for UnweightedClassic DP Master Patterns: 0/1 Knapsack, Coin Change & LCS

Practice Quiz

Test your understanding of this lesson with 5 questions. Each question has one correct answer.

PreviousNext
PrevNext