Dynamic Programming — Explained with Examples

Dynamic programming solves complex problems by breaking them into overlapping subproblems, storing results to avoid redundant computation.

Dynamic Programming (DP) applies when a problem has optimal substructure (optimal solution built from optimal solutions of subproblems) and overlapping subproblems (same subproblems recur). Two approaches: top-down with memoization (recursion + caching) and bottom-up tabulation (iterative table filling). Classic DP problems include Fibonacci, knapsack, longest common subsequence, and edit distance.

Think of DP like planning a road trip with a notebook. Instead of recalculating the distance to each city every time you pass it, you write it down once and look it up later. The notebook (DP table) saves you from repeating the same calculation thousands of times.

Bottom-up DP typically starts with the smallest subproblems and builds upward. The approach eliminates recursion overhead and avoids stack overflow, but requires careful ordering.

# Fibonacci with DP (bottom-up)
def fibonacci(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]

# Fibonacci with memoization (top-down)
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(fibonacci(50))  # 12586269025

DP requires practice to recognize patterns: whether you are maximizing/minimizing, counting possibilities, or checking feasibility. Common DP patterns include 0/1 knapsack, unbounded knapsack, LCS, and matrix chain multiplication.

Recursion, Divide and Conquer, Greedy Algorithm, Backtracking

Recursion Fundamentals