Dynamic Programming (DP) | Essential Algorithm for Coding Interviews

Introduction

”Don’t Repeat the Same Calculation”

Dynamic Programming (DP) stores duplicate calculations to optimize O(2ⁿ) → O(n).

---

1. DP Basics

Understanding with Fibonacci

Problem: Find nth Fibonacci number

# ❌ Naive recursion (O(2ⁿ) - very slow!)
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n-1) + fib_naive(n-2)

print(fib_naive(40))  # Takes tens of seconds!

Problem: Same values calculated multiple times

fib(5)
├─ fib(4)
│  ├─ fib(3)
│  │  ├─ fib(2)  ← Duplicate!
│  │  └─ fib(1)
│  └─ fib(2)  ← Duplicate!
└─ fib(3)  ← Duplicate!
   ├─ fib(2)
   └─ fib(1)

---

2. Top-Down (Memoization)

Recursion + Caching

Memoization stores computed fib(k) values in a dictionary, retrieving stored values instead of recalculating. Like memorizing phone numbers instead of looking them up each time.

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

print(fib_memo(40))  # Instant! (<0.001s)

# Naive vs Memoization:
# fib_naive(40): 2^40 ≈ 1 trillion calculations (tens of seconds)
# fib_memo(40): 40 calculations (instant)

Memoization Caution:

# ❌ Wrong: memo as default argument
def fib_bad(n, memo={}):
    # Default arguments created once at function definition
    # Shared across multiple calls
    pass

# ✅ Correct: memo as None
def fib_good(n, memo=None):
    if memo is None:
        memo = {}
    
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_good(n-1, memo) + fib_good(n-2, memo)
    return memo[n]

Python Decorator

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_cached(n):
    if n <= 1:
        return n
    return fib_cached(n-1) + fib_cached(n-2)

print(fib_cached(100))  # Very fast

---

3. Bottom-Up (Tabulation)

Iteration + Table

Bottom-up solves small problems first, filling table sequentially:

# ✅ Bottom-Up (O(n), faster than recursion)
def fib_dp(n):
    if n <= 1:
        return n
    
    # DP table
    dp = [0] * (n + 1)
    
    # Initial values
    dp[0] = 0
    dp[1] = 1
    
    # Solve from small to large
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

print(fib_dp(100))  # Instant

Top-Down vs Bottom-Up:

# Top-Down (Memoization)
# Pros:
#   - Intuitive with recursion
#   - Computes only needed values
# Cons:
#   - Recursion overhead
#   - Stack overflow risk
#   - Relatively slower

# Bottom-Up (Tabulation)
# Pros:
#   - Faster with iteration
#   - No stack overflow
#   - Easy space optimization
# Cons:
#   - Computes all subproblems
#   - Recurrence relation may be harder to find

# Bottom-up more common in practice

Space Optimization

# ✅ O(1) space
def fib_optimized(n):
    if n <= 1:
        return n
    
    prev2, prev1 = 0, 1
    
    for _ in range(2, n + 1):
        current = prev1 + prev2
        prev2, prev1 = prev1, current
    
    return prev1

print(fib_optimized(100))

---

4. DP Problem Patterns

Pattern 1: 1D DP

Example: Climbing Stairs

def climb_stairs(n):
    """
    Count ways to climb n stairs (1 or 2 steps at a time)
    
    n=1: 1 way (1 step)
    n=2: 2 ways (1+1, 2)
    n=3: 3 ways (1+1+1, 1+2, 2+1)
    """
    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]

print(climb_stairs(5))  # 8

Space Optimized:

def climb_stairs_optimized(n):
    if n <= 2:
        return n
    
    prev2, prev1 = 1, 2
    
    for i in range(3, n + 1):
        current = prev1 + prev2
        prev2, prev1 = prev1, current
    
    return prev1

Pattern 2: 2D DP

Example: Minimum Path Sum

def min_path_sum(grid):
    """
    Find minimum sum path from (0,0) to (n-1,m-1)
    """
    n, m = len(grid), len(grid[0])
    dp = [[0] * m for _ in range(n)]
    
    dp[0][0] = grid[0][0]
    
    # First row
    for j in range(1, m):
        dp[0][j] = dp[0][j-1] + grid[0][j]
    
    # First column
    for i in range(1, n):
        dp[i][0] = dp[i-1][0] + grid[i][0]
    
    # Rest
    for i in range(1, n):
        for j in range(1, m):
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
    
    return dp[n-1][m-1]

# Test
grid = [
    [1, 3, 1],
    [1, 5, 1],
    [4, 2, 1]
]
print(min_path_sum(grid))  # 7 (1→3→1→1→1)

Pattern 3: Knapsack Problem

def knapsack(weights, values, capacity):
    """
    0-1 Knapsack problem
    
    Problem: Maximize value within capacity
    Constraint: Each item can be taken 0 or 1 time
    """
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(capacity + 1):
            # Choice 1: Don't take item i
            dp[i][w] = dp[i-1][w]
            
            # Choice 2: Take item i
            if weights[i-1] <= w:
                dp[i][w] = max(
                    dp[i][w],
                    dp[i-1][w - weights[i-1]] + values[i-1]
                )
    
    return dp[n][capacity]

# Test
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8
print(knapsack(weights, values, capacity))  # 10

Space Optimized (1D array):

def knapsack_optimized(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)
    
    for i in range(n):
        # Update from back to prevent overwriting
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[capacity]

---

5. DP Problem Approach

Step 1: Identify DP

✅ DP signals:
- "max/min value"
- "count ways"
- "is possible"
- Overlapping subproblems

❌ Not DP:
- Solvable with greedy
- Simple simulation

Step 2: Define Recurrence

# Example: Climbing stairs
# dp[i] = ways to reach stair i
# dp[i] = dp[i-1] + dp[i-2]

Step 3: Set Initial Values

# Example: Climbing stairs
dp[1] = 1  # 1 stair: 1 way
dp[2] = 2  # 2 stairs: 2 ways

Step 4: Choose Implementation

# Top-Down: When recursion is natural
# Bottom-Up: When iteration is clear (faster)

---

6. Common DP Problems

Longest Increasing Subsequence (LIS)

def length_of_lis(nums):
    """
    Find length of longest increasing subsequence
    [10, 9, 2, 5, 3, 7, 101, 18] → 4 ([2, 3, 7, 101])
    """
    if not nums:
        return 0
    
    n = len(nums)
    dp = [1] * n  # Each element is a subsequence of length 1
    
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    
    return max(dp)

# Test
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(length_of_lis(nums))  # 4

Coin Change

def coin_change(coins, amount):
    """
    Find minimum coins needed to make amount
    coins=[1,2,5], amount=11 → 3 (5+5+1)
    """
    dp = [float('inf')] * (amount + 1)
    dp[0] = 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

# Test
print(coin_change([1, 2, 5], 11))  # 3

---

Summary

Key Points

1. DP: Store duplicate calculations, O(2ⁿ) → O(n)
2. Top-Down: Recursion + memoization
3. Bottom-Up: Iteration + table (faster)
4. Recurrence: dp[i] = f(dp[i-1], dp[i-2], …)

Problem Identification

Signal	Example
”Maximum/Minimum”	Max profit, min cost
”Count ways”	Number of paths
”Is possible”	Can reach target
Overlapping subproblems	Fibonacci, LCS

---

Recommended Problems

Beginner

• LeetCode 70: Climbing Stairs
• LeetCode 509: Fibonacci Number
• LeetCode 746: Min Cost Climbing Stairs

Intermediate

• LeetCode 322: Coin Change
• LeetCode 300: Longest Increasing Subsequence
• LeetCode 64: Minimum Path Sum

Advanced

• LeetCode 72: Edit Distance
• LeetCode 312: Burst Balloons
• LeetCode 1143: Longest Common Subsequence

---

Related Posts

• DP Patterns | Problem-Solving Strategies
• Greedy Algorithms | Complete Guide
• Backtracking | Exhaustive Search

---

Keywords

Dynamic Programming, DP, Memoization, Tabulation, Top-Down, Bottom-Up, Fibonacci, Knapsack, LIS, Coding Interview, Algorithm, Optimization