DSA Dynamic Programming

What Is Dynamic Programming?

Dynamic programming (DP) solves problems by breaking them into smaller subproblems, solving each one once, and storing its result so it never has to be recomputed. DP applies when a problem has two properties: optimal substructure, meaning an optimal solution can be built from optimal solutions to subproblems, and overlapping subproblems, meaning a naive approach would solve the same smaller problem again and again.

• Optimal substructure - an optimal solution can be constructed from optimal solutions of its subproblems
• Overlapping subproblems - the same smaller problems are solved repeatedly in a naive recursive approach
• Memoization - top-down caching of subproblem results, usually with a dictionary
• Tabulation - bottom-up iterative computation, usually with an array or table

Consider computing the nth Fibonacci number recursively. Calculating fib(5) requires fib(4) and fib(3), but fib(4) itself requires fib(3) and fib(2) — so fib(3) gets computed twice. As n grows, the number of repeated calculations explodes exponentially, which is exactly the overlapping-subproblems pattern DP is built to fix.

def fib_naive(n):
    # Recomputes the same values many times over.
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

print(fib_naive(10))  # 55

Memoization vs. Tabulation

Memoization keeps the natural recursive structure but adds a cache that stores the result of each subproblem the first time it is solved. Later calls with the same argument return instantly from the cache instead of recomputing the whole subtree.

def fib_memo(n, cache=None):
    if cache is None:
        cache = {}
    if n in cache:
        return cache[n]
    if n <= 1:
        return n
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]

print(fib_memo(50))  # 12586269025

Tabulation instead solves subproblems iteratively, starting from the smallest base cases and building up to the final answer in an array or table. It avoids recursion entirely, which removes call-stack overhead and the risk of hitting Python's recursion limit.

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

print(fib_tabulation(50))  # 12586269025