Dynamic Programming

Dynamic Programming (DP) is an algorithmic paradigm that solves complex problems by breaking them down into simpler subproblems and storing their solutions.

Core Concepts

1. Optimal Substructure

A problem has optimal substructure if an optimal solution can be constructed from optimal solutions of its subproblems.

2. Overlapping Subproblems

A problem has overlapping subproblems if the same subproblems are solved multiple times.

Approaches

Top-Down (Memoization)

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

Bottom-Up (Tabulation)

def fibonacci_tab(n):
    if n <= 1:
        return 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]

Classic Problems

1. Knapsack Problem
2. Longest Common Subsequence
3. Edit Distance
4. Coin Change
5. Matrix Chain Multiplication

Problem-Solving Steps

1. Define the state
2. Identify the recurrence relation
3. Determine base cases
4. Choose implementation (memoization vs tabulation)
5. Optimize space if possible

When to Use DP

• Problem asks for optimization (maximum/minimum)
• Problem asks for counting total ways
• Problem involves making decisions at each step
• Current decision depends on previous decisions

Optimization Tips

1. Space optimization (rolling array)
2. State compression
3. Precomputation
4. Pruning invalid states