13  Dynamic Programming

Dynamic Programming

Breaking complex problems down. Mastering the art of memoization and tabulation.

14 Dynamic Programming: Taming the Beast

DP was the boss battle of my DSA journey. It felt like magic until I realized it’s just “smart recursion”.

My realization: Don’t repeat yourself. If you’ve solved a subproblem, save the answer! That’s it. That’s the whole trick.

Dynamic Programming (DP) is a method for solving complex problems by breaking them down into simpler subproblems. It’s particularly useful for optimization problems where the solution can be constructed from solutions to overlapping subproblems.

14.1 Core Concepts

14.1.1 1. Overlapping Subproblems

• Problems that can be broken down into smaller subproblems
• Solutions to subproblems are reused multiple times
• Example: Fibonacci sequence

14.1.2 2. Optimal Substructure

• An optimal solution can be constructed from optimal solutions to its subproblems
• Example: Shortest path in a graph

14.2 Approaches

14.2.1 1. Top-down (Memoization)

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

14.2.2 2. Bottom-up (Tabulation)

def fib(n):
    if n <= 2:
        return 1
    dp = [0] * (n + 1)
    dp[1] = dp[2] = 1
    for i in range(3, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

14.3 Common DP Patterns

14.3.1 1. 0/1 Knapsack

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(values[i-1] + dp[i-1][w-weights[i-1]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]
    
    return dp[n][capacity]

14.3.2 2. Longest Common Subsequence (LCS)

def lcs(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            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])
    
    return dp[m][n]

14.3.3 3. Coin Change

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)
    
    return dp[amount] if dp[amount] != float('inf') else -1

14.4 Common Problems

1. Climbing Stairs
2. House Robber
3. Longest Increasing Subsequence
4. Word Break
5. Unique Paths

14.5 Time Complexity

Problem Type	Time Complexity	Space Complexity
1D DP	O(n)	O(n) or O(1)
2D DP	O(m*n)	O(m*n) or O(n)
Knapsack	O(n*W)	O(n*W) or O(W)
LCS	O(m*n)	O(m*n) or O(n)

14.6 Tips for Interviews

1. Start with a recursive solution first
2. Identify the base cases
3. Look for overlapping subproblems
4. Decide between top-down and bottom-up approach
5. Optimize space when possible
6. Practice drawing the DP table for better visualization