Dynamic Programming

Solve complex problems by breaking into subproblems.

Key Concepts

Overlapping Subproblems

Problems break into reusable subproblems.

Optimal Substructure

Optimal solution contains optimal subproblems.

Approaches

Top-Down (Memoization)

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

Bottom-Up (Tabulation)

def fib(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

• Fibonacci
• 0/1 Knapsack
• Longest Common Subsequence
• Coin Change

More detailed guides coming soon!