Dynamic Programming (DP) Fundamentals

Dynamic Programming solves complex problems by breaking them into simpler overlapping subproblems and storing results to avoid redundant calculations.

Key Concepts

1. Overlapping Subproblems

The same subproblems are solved multiple times.

2. Optimal Substructure

Optimal solution contains optimal solutions to subproblems.

Fibonacci: Naive vs DP

Naive Recursion - O(2^n)

def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n-1) + fib_naive(n-2)  # Repeats calculations!

Memoization (Top-Down DP) - O(n)

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]

Tabulation (Bottom-Up DP) - O(n)

def fib_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]

Memoization vs Tabulation

Quiz

Key Takeaways

✅ DP optimizes by storing subproblem results
✅ Memoization - top-down with caching
✅ Tabulation - bottom-up table filling
✅ Transforms O(2^n) to O(n) for many problems

Essential for optimization problems! 🚀