Skip to main content

Dynamic Programming: From Zero to Hero

ยท 16 min read
  1. ๐ŸŽฏ What is Dynamic Programming?
  2. ๐Ÿ“Š The Core Idea
  3. ๐Ÿ”„ Two Approaches to DP (Top-Down vs Bottom-Up)
  4. ๐Ÿ”‘ Two Key Properties of DP
  5. ๐Ÿงฉ Example 1: Fibonacci Numbers
  6. ๐Ÿ—๏ธ DP Framework: 5-Step Process
  7. ๐Ÿงฉ Example 2: Climbing Stairs
  8. ๐Ÿ“ฆ DP Categories & Patterns
  9. ๐Ÿงฉ Example 3: Unique Paths (2D DP)
  10. ๐Ÿ’ฐ Example 4: Coin Change (Classic DP)
  11. 1D vs 2D DP (Very Important)
  12. ๐Ÿ” How to Identify DP Problems
  13. ๐Ÿ› ๏ธ DP Implementation Patterns
  14. ๐Ÿšจ Common Mistakes & How to Avoid Them
  15. ๐Ÿ”„ Memoization vs Tabulation
  16. ๐ŸŽ“ DP Problem-Solving Checklist
  17. ๐Ÿ“Š Space Optimization Techniques
  18. ๐ŸŽฏ Practice Problems by Difficulty
  19. ๐Ÿง  Mental Models for DP
  20. ๐Ÿ“š Resources for Practice
  21. ๐Ÿ’ช Final Summary

๐ŸŽฏ What is Dynamic Programming?โ€‹

Dynamic Programming (DP) is a method for solving complex problems by breaking them down into simpler subproblems, solving each subproblem just once, and storing their solutions.

Three key concepts:

  1. A problem can be broken into smaller subproblems
  2. Those subproblems repeat
  3. We can store their answers and reuse them

๐Ÿ”‘ Oneโ€‘sentence definition:

Dynamic Programming = Recursion + Memory

๐Ÿ’ก Simple Analogy: Imagine climbing stairs. To reach step 10, you need to know how to reach step 9. To reach step 9, you need step 8... DP remembers solutions to these smaller steps!


๐Ÿ“Š The Core Ideaโ€‹

Solving big problem
โ†“
Break into smaller problems
โ†“
Solve & remember solutions
โ†“
Reuse solutions to solve bigger problem

Key Properties of DP Problems:โ€‹

  1. Optimal Substructure: Optimal solution can be constructed from optimal solutions of subproblems

    • The "Optimal" solution to the big problem can be constructed from the "Optimal" solutions of its subproblems.
    • If you want the shortest path from A to C, and it goes through B, the path must include the shortest path from A to B.
  2. Overlapping Subproblems: Same subproblems are solved multiple times

    • This means the problem can be broken down into smaller versions of itself, and those smaller versions repeat.

๐Ÿ”„ Two Approaches to DP (Top-Down vs Bottom-Up)โ€‹

There are two ways to implement DP. Think of them as "The Lazy Way" and "The Organized Way."

Method 1: Top-Down (Memoization)โ€‹

You start with the big problem and break it down. If you've solved a subproblem before, you look up the answer in your "notebook" (usually a dictionary or array).

  • Vibe: "I'll solve it when I need it, and save the answer for later."
  • Tool: Recursion + Cache.
flowchart LR
Call --> CheckCache
CheckCache -->|Found| Return
CheckCache -->|Not Found| Compute
Compute --> Save
Save --> Return
memo = {}

def fib(n):
if n <= 1:
return n
if n in memo:
return memo[n]
memo[n] = fib(n-1) + fib(n-2)
return memo[n]

Method 2: Bottom-Up (Tabulation)โ€‹

You start with the smallest possible subproblems (base cases) and fill out a table until you reach the goal.

  • Vibe: "Let's build a foundation from the ground up."
  • Tool: Iteration (Loops) + Table (Array/Grid).
flowchart LR
Base --> DP1 --> DP2 --> DP3 --> Answer
def fib(n):
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]

โœ… Pros: No recursion, often faster


๐Ÿ”‘ Two Key Properties of DP (Must Memorize)โ€‹

1. Overlapping Subproblemsโ€‹

Same subproblem appears again and again

graph TD
A["fib(5)"] --> B["fib(4)"]
A --> C["fib(3)"]
B --> C

2. Optimal Substructureโ€‹

The optimal solution of a problem depends on optimal solutions of subproblems

Examples:

  • Shortest path
  • Maximum profit
  • Minimum steps

๐Ÿงฉ Example 1: Fibonacci Numbersโ€‹

Problem: Find the nth Fibonacci numberโ€‹

fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2) for n > 1

Call Tree Explosionโ€‹

flowchart TD
F5 --> F4
F5 --> F3
F4 --> F3
F4 --> F2
F3 --> F2
F3 --> F1

โŒ Problem: fib(3) and fib(2) are computed multiple times

1. Brute Force (Recursive) - โŒ Inefficientโ€‹

def fib_naive(n):
if n <= 1:
return n
return fib_naive(n-1) + fib_naive(n-2)
# Time: O(2โฟ) - Exponential!

2. Memoization (Top-Down DP) - โœ… Efficientโ€‹

def fib_memo(n, memo={}):
if n <= 1:
return n
if n not in memo:
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]
# Time: O(n), Space: O(n)

3. Tabulation (Bottom-Up DP) - โœ… Most Efficientโ€‹

def fib_tab(n):
if n <= 1:
return n

# 1. State: dp[i] is the i-th Fibonacci number
dp = [0] * (n + 1)

# 2. Base Cases
dp[0] = 0
dp[1] = 1

# 4. Order: 2 to n
for i in range(2, n + 1):
# 3. Recurrence Relation
dp[i] = dp[i-1] + dp[i-2]

# 5. Final Answer
return dp[n]
# Time: O(n), Space: O(n)

Visualization:

Index: 0 1 2 3 4 5
dp = [0, 1, 0, 0, 0, 0] # Initial
i=2: dp[2] = 1 + 0 = 1
dp = [0, 1, 1, 0, 0, 0]
i=3: dp[3] = 1 + 1 = 2
dp = [0, 1, 1, 2, 0, 0]
i=4: dp[4] = 2 + 1 = 3
dp = [0, 1, 1, 2, 3, 0]
i=5: dp[5] = 3 + 2 = 5
dp = [0, 1, 1, 2, 3, 5]

4. Space Optimized - โœ… O(1) Spaceโ€‹

def fib_optimized(n):
if n <= 1:
return n
prev2, prev1 = 0, 1 # F(0), F(1)
for i in range(2, n + 1):
current = prev1 + prev2
prev2, prev1 = prev1, current
return prev1
# Time: O(n), Space: O(1)

๐Ÿ—๏ธ DP Framework: 5-Step Processโ€‹

Step 1: Define the Stateโ€‹

What does dp[i] represent?

Example: dp[i] = i-th Fibonacci number

Step 2: Define the Base Casesโ€‹

What are the smallest problems with known solutions?

Example: dp[0] = 0, dp[1] = 1

Step 3: Define the Recurrence Relation (What are the choices?)โ€‹

How does dp[i] depend on smaller states?

Example: dp[i] = dp[i-1] + dp[i-2]

Step 4: Determine Order of Computation (What is the transition?)โ€‹

Should we go bottom-up or top-down?

Example: Compute from dp[0] to dp[n]

Step 5: Return the Answerโ€‹

Which state contains the final answer?

Example: Return dp[n]


๐Ÿงฉ Example 2: Climbing Stairsโ€‹

Problem: You can climb 1 or 2 steps at a time. How many ways to reach the top?โ€‹

Observation: This is Fibonacci! ways(n) = ways(n-1) + ways(n-2)

n = 1: [1] โ†’ 1 way
n = 2: [1,1], [2] โ†’ 2 ways
n = 3: [1,1,1], [1,2], [2,1] โ†’ 3 ways
n = 4: โ†’ 5 ways

DP Solution:โ€‹

def climbStairs(n):
if n <= 2:
return n
dp = [0] * (n + 1)
dp[1] = 1 # 1 way to reach step 1
dp[2] = 2 # 2 ways to reach step 2
for i in range(3, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]

# Space optimized:
def climbStairs_opt(n):
if n <= 2:
return n
prev2, prev1 = 1, 2
for _ in range(3, n + 1):
current = prev1 + prev2
prev2, prev1 = prev1, current
return prev1

State & Transition:โ€‹

  • State: dp[i] = number of ways to reach step i
  • Transition: dp[i] = dp[i-1] + dp[i-2]
graph LR
S0 --> S1
S0 --> S2
S1 --> S2
S1 --> S3

Visual Explanation:

To reach step i:
1. Come from step i-1 (take 1 step)
2. Come from step i-2 (take 2 steps)
Total ways(i) = ways(i-1) + ways(i-2)

๐Ÿ“ฆ DP Categories & Patternsโ€‹

1. 1D DP (Linear Problems)โ€‹

โ”Œโ”€โ”€โ”€โ”ฌโ”€โ”€โ”€โ”ฌโ”€โ”€โ”€โ”ฌโ”€โ”€โ”€โ”ฌโ”€โ”€โ”€โ”
โ”‚dp0โ”‚dp1โ”‚dp2โ”‚dp3โ”‚dp4โ”‚
โ””โ”€โ”€โ”€โ”ดโ”€โ”€โ”€โ”ดโ”€โ”€โ”€โ”ดโ”€โ”€โ”€โ”ดโ”€โ”€โ”€โ”˜
โ†“ depends on previous 1-2 elements

Examples: Fibonacci, Climbing Stairs, House Robber

2. 2D DP (Grid/Matrix Problems)โ€‹

Problem: You are at the top-left of a grid. You can only move Right or Down. How many ways can you reach the bottom-right?

To get to any cell, you must have come from either the Top or the Left. Each cell in the table above stores the number of ways to reach that specific spot. We fill it row by row, adding the values from the neighbors we already calculated.

0 1 2 3
0 โ”Œโ”€โ”€โ”€โ”ฌโ”€โ”€โ”€โ”ฌโ”€โ”€โ”€โ”ฌโ”€โ”€โ”€โ”
โ”‚ S โ”‚ โ†’ โ”‚ โ†’ โ”‚ โ†’ โ”‚
1 โ”œโ”€โ”€โ”€โ”ผโ”€โ”€โ”€โ”ผโ”€โ”€โ”€โ”ผโ”€โ”€โ”€โ”ค
โ”‚ โ†“ โ”‚ โ†˜ โ”‚ โ†˜ โ”‚ โ†˜ โ”‚
2 โ”œโ”€โ”€โ”€โ”ผโ”€โ”€โ”€โ”ผโ”€โ”€โ”€โ”ผโ”€โ”€โ”€โ”ค
โ”‚ โ†“ โ”‚ โ†˜ โ”‚ โ†˜ โ”‚ E โ”‚
3 โ””โ”€โ”€โ”€โ”ดโ”€โ”€โ”€โ”ดโ”€โ”€โ”€โ”ดโ”€โ”€โ”€โ”˜

Examples: Unique Paths, Minimum Path Sum

3. Knapsack DP (Selection Problems)โ€‹

Choose items with constraints (weight, value)

4. Interval DPโ€‹

Problems involving intervals/ranges

5. Tree DPโ€‹

DP on tree structures


๐Ÿงฉ Example 3: Unique Paths (2D DP)โ€‹

Problem: Robot at top-left, can only move right or down. How many unique paths to bottom-right?โ€‹

Grid: 3ร—3
S โ†’ โ†’
โ†“ โ†˜
โ†“ โ†˜ E
Answer: 6 paths

DP Solution:โ€‹

def uniquePaths(m, n):
# dp[i][j] = ways to reach cell (i,j)
dp = [[0] * n for _ in range(m)]

# Base cases
for i in range(m):
dp[i][0] = 1 # First column
for j in range(n):
dp[0][j] = 1 # First row

# Fill DP table
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]

return dp[m-1][n-1]

Visualization (3ร—3 grid):

Initial:
1 1 1
1 0 0
1 0 0

After filling:
1 1 1
1 2 3
1 3 6 โ† Answer: 6

Explanation:

  • Can only come from above or left
  • dp[i][j] = dp[i-1][j] + dp[i][j-1]

๐Ÿ’ฐ Example 4: Coin Change (Classic DP)โ€‹

Problem: Minimum coins to make amountโ€‹

Coins: [1, 2, 5]
Amount: 11
Answer: 3 (5 + 5 + 1)

State:โ€‹

dp[x] = minimum coins needed to make amount x

Transition:โ€‹

dp[x] = min(dp[x - coin] + 1)

flowchart TD
A[Amount x]
A -->|Try coin 1| B[x-1]
A -->|Try coin 2| C[x-2]
A -->|Try coin 5| D[x-5]

DP Solution:โ€‹

def coinChange(coins, amount):
# dp[i] = min coins to make amount i
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # 0 coins needed for amount 0

for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)

return dp[amount] if dp[amount] != float('inf') else -1

Step-by-step (coins=[1,2,5], amount=11):

dp[0] = 0
dp[1] = min(dp[0]+1) = 1
dp[2] = min(dp[1]+1, dp[0]+1) = min(2,1) = 1
dp[3] = min(dp[2]+1, dp[1]+1) = min(2,2) = 2
...
dp[11] = min(dp[10]+1, dp[9]+1, dp[6]+1) = min(2+1, 3+1, 2+1) = 3

1D vs 2D DP (Very Important)โ€‹

1D DPโ€‹

graph LR
dp0 --> dp1 --> dp2 --> dp3

Examples: Fibonacci, Climbing stairs, Coin change

2D DPโ€‹

graph TD
dp00 --> dp01 --> dp02
dp10 --> dp11 --> dp12
dp20 --> dp21 --> dp22

Examples: Knapsack, Longest Common Subsequence, Edit Distance


Classic 2D DP: Longest Common Subsequence (LCS)โ€‹

State:โ€‹

dp[i][j] = LCS length of text1[:i] and text2[:j]

Transition:โ€‹

if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
flowchart TD
A[dp[i-1][j]] --> C[dp[i][j]]
B[dp[i][j-1]] --> C
D[dp[i-1][j-1]] --> C

Space Optimization (Advanced but Powerful)โ€‹

Many DP problems only depend on previous row

flowchart LR
Row1 --> Row2 --> Row3

So you can reduce:

  • O(nยฒ) โ†’ O(n)

DP Problem Pattern Mapโ€‹

mindmap
root((Dynamic Programming))
1D DP
Fibonacci
Stairs
Coin Change
2D DP
Knapsack
LCS
Edit Distance
State Compression
Bitmask DP
Interval DP
Burst Balloons

๐Ÿ” How to Identify DP Problemsโ€‹

Ask These Questions:โ€‹

  1. Can it be broken into subproblems?
  2. Do subproblems overlap? (Would recursion repeat calculations?)
  3. Is there optimal substructure? (Can we build optimal solution from optimal subproblems?)

Common DP Problem Patterns:โ€‹

1. "Count the number of ways..." โ†’ Often DP
2. "Find minimum/maximum..." โ†’ Often DP
3. "Find if possible..." โ†’ Often DP
4. Grid/matrix problems โ†’ Often 2D DP
5. String problems โ†’ Often 2D DP

How to Recognize a DP Problem (Interview Gold โญ)โ€‹

Look for these keywords:

  • "maximum / minimum"
  • "number of ways"
  • "longest / shortest"
  • "can you reach"
  • "optimal"

๐Ÿ› ๏ธ DP Implementation Patternsโ€‹

Pattern 1: Fibonacci Styleโ€‹

# dp[i] depends on dp[i-1], dp[i-2]
dp = [0] * (n+1)
dp[0], dp[1] = base_cases
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]

Pattern 2: Grid DPโ€‹

# dp[i][j] depends on dp[i-1][j], dp[i][j-1]
dp = [[0]*cols for _ in range(rows)]
# Initialize first row/col
for i in range(rows):
for j in range(cols):
dp[i][j] = dp[i-1][j] + dp[i][j-1]

Pattern 3: Knapsack Styleโ€‹

# dp[i][w] = max value with first i items and weight w
dp = [[0]*(W+1) for _ in range(n+1)]
for i in range(1, n+1):
for w in range(1, W+1):
if weight[i-1] <= w:
dp[i][w] = max(dp[i-1][w],
dp[i-1][w-weight[i-1]] + value[i-1])
else:
dp[i][w] = dp[i-1][w]

Pattern 4: LCS (Longest Common Subsequence)โ€‹

# dp[i][j] = LCS of first i chars of A and j chars of B
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, m+1):
if A[i-1] == B[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])

๐Ÿšจ Common Mistakes & How to Avoid Themโ€‹

Mistake 1: Not defining state clearlyโ€‹

Fix: Write down what dp[i] means before coding

Mistake 2: Wrong base casesโ€‹

Fix: Test with smallest inputs (n=0, n=1)

Mistake 3: Off-by-one errorsโ€‹

Fix: Use 0-indexed or 1-indexed consistently

Mistake 4: Forgetting to initializeโ€‹

Fix: Always initialize DP array with appropriate values

Mistake 5: Wrong recurrence relationโ€‹

Fix: Draw small examples to verify logic


๐Ÿ”„ Memoization vs Tabulationโ€‹

Memoization (Top-Down)โ€‹

def solve(n, memo={}):
if n in memo: return memo[n]
if base_case: return value
memo[n] = solve(n-1) + solve(n-2)
return memo[n]

Pros:

  • More intuitive (like recursion)
  • Only computes needed states

Cons:

  • Recursion depth limit
  • Function call overhead

Tabulation (Bottom-Up)โ€‹

dp = [0]*(n+1)
for i in range(1, n+1):
dp[i] = dp[i-1] + dp[i-2]

Pros:

  • No recursion limit
  • Often faster
  • Easier to optimize space

Cons:

  • Might compute unnecessary states
  • Less intuitive initially

๐ŸŽ“ DP Problem-Solving Checklistโ€‹

Before Coding:โ€‹

  • Identify this is a DP problem
  • Define state variables clearly
  • Write recurrence relation on paper
  • Determine base cases
  • Decide memoization vs tabulation

While Coding:โ€‹

  • Initialize DP table properly
  • Handle edge cases
  • Verify recurrence with small example
  • Check indices/off-by-one errors

After Coding:โ€‹

  • Test with given examples
  • Test with edge cases (empty, minimum size)
  • Consider space optimization
  • Analyze time/space complexity

๐Ÿ“Š Space Optimization Techniquesโ€‹

1. Rolling Array (for dependencies on few previous states)โ€‹

# Before: dp[i] depends on dp[i-1], dp[i-2]
# After: Keep only last 2 values
prev2, prev1 = 0, 1
for i in range(2, n+1):
current = prev1 + prev2
prev2, prev1 = prev1, current

2. Reuse Input Array (if allowed)โ€‹

# Modify input array in place as DP table

3. Alternate Rows in 2D DPโ€‹

# When dp[i][j] only depends on previous row
dp_prev = [0]*n
dp_curr = [0]*n
for i in range(1, m):
for j in range(1, n):
dp_curr[j] = dp_prev[j] + dp_curr[j-1]
dp_prev, dp_curr = dp_curr, dp_prev

๐Ÿ“ DP Templateโ€‹

def dp_solution(inputs):
# Step 1: Identify state variables
# dp[i] or dp[i][j] or dp[i][j][k]...

# Step 2: Create DP table
n = len(inputs)
dp = [0] * (n + 1) # or 2D array

# Step 3: Base cases
dp[0] = base_value
# or initialize first row/col

# Step 4: State transition
for i in range(1, n + 1):
for option in options:
dp[i] = max/min(dp[i], dp[prev_state] + something)
# or dp[i] = dp[i-1] + dp[i-2] etc.

# Step 5: Return answer
return dp[n] # or dp[-1][-1] for 2D

๐ŸŽฏ Practice Problems by Difficultyโ€‹

Beginner Level:โ€‹

  1. Fibonacci Number (LeetCode 509)
  2. Climbing Stairs (LeetCode 70)
  3. Best Time to Buy/Sell Stock (LeetCode 121)
  4. Maximum Subarray (LeetCode 53)

Intermediate Level:โ€‹

  1. House Robber (LeetCode 198)
  2. Coin Change (LeetCode 322)
  3. Longest Increasing Subsequence (LeetCode 300)
  4. Unique Paths (LeetCode 62)

Advanced Level:โ€‹

  1. Edit Distance (LeetCode 72)
  2. Longest Common Subsequence (LeetCode 1143)
  3. Word Break (LeetCode 139)
  4. Knapsack Problems

๐Ÿง  Mental Models for DPโ€‹

Model 1: The "Building Up" Modelโ€‹

Think: "If I know solutions for all smaller problems, how do I solve the current one?"

Model 2: The "Decision Tree" Modelโ€‹

At each step, you make a choice. DP finds the optimal path through the tree.

Model 3: The "Caching" Modelโ€‹

Remember expensive computations so you don't repeat them.

Model 4: The "State Machine" Modelโ€‹

Your state represents where you are in the problem. Transitions represent decisions.


๐Ÿ“š Resources for Practiceโ€‹

Interactive Platforms:โ€‹

  • LeetCode: Filter by "Dynamic Programming" tag
  • AtCoder DP Contest: 26 classic DP problems
  • CSES Problem Set: Excellent DP section
  1. Fibonacci & climbing stairs
  2. Grid problems (unique paths)
  3. Knapsack problems
  4. String DP (LCS, edit distance)
  5. Advanced DP (tree DP, bitmask DP)

๐Ÿ’ช Final Summary: DP Mastery Pathโ€‹

Level 1: Foundationโ€‹

  • Understand recursion with overlapping subproblems
  • Learn memoization pattern
  • Practice Fibonacci, climbing stairs

Level 2: Core Patternsโ€‹

  • Master 1D DP patterns
  • Learn to define states and transitions
  • Practice house robber, coin change

Level 3: Advanced Patternsโ€‹

  • Master 2D DP (grid problems)
  • Understand knapsack patterns
  • Practice unique paths, LCS

Level 4: Optimizationโ€‹

  • Space optimization techniques
  • Time complexity analysis
  • Real-world DP applications

Level 5: Masteryโ€‹

  • Recognize DP patterns quickly
  • Derive recurrence relations
  • Solve complex DP problems

Golden Rule: If you see overlapping subproblems and optimal substructure, think DP!

Remember: Practice is key. Start with simple problems and gradually increase difficulty. Draw diagrams, write recurrence relations, and don't get discouraged!

You've got this! ๐Ÿš€ Every DP master started where you are now. Keep practicing!