Dynamic Programming Fundamentals

Dynamic Programming (DP) solves problems by breaking them into smaller overlapping subproblems, solving each subproblem once, and storing the result to avoid redundant work.

Two conditions must hold:

Optimal substructure: the optimal solution can be built from optimal solutions to subproblems.
Overlapping subproblems: the same subproblem is solved multiple times in a naive recursion.

Motivating Example: Fibonacci

Naive recursion recomputes fib(3) multiple times:

fib(5)
  fib(4)
    fib(3)
      fib(2)  ← computed again
      fib(1)
    fib(2)    ← duplicate
  fib(3)      ← duplicate subtree

Top-down (memoization): cache results as they are computed.

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n: int) -> int:
    if n <= 1: return n
    return fib(n - 1) + fib(n - 2)

Bottom-up (tabulation): fill a table from base cases upward.

def fib(n: int) -> int:
    if n <= 1: return n
    dp = [0, 1]
    for i in range(2, n + 1):
        dp.append(dp[-1] + dp[-2])
    return dp[n]

Both approaches reduce time from $O(2^N)$ to $O(N)$ .

Top-Down vs. Bottom-Up

	Top-Down (Memoization)	Bottom-Up (Tabulation)
Code style	Recursive + cache	Iterative + table
When to use	Natural recursion, large sparse state space	Tight loops, space optimization
Space	Call stack + cache	Table only (can often compress to $O(1)$ )

Common DP Patterns

1. Linear DP

State depends on a single index. dp[i] = best answer for the first i elements.

# Longest Increasing Subsequence
dp = [1] * len(nums)
for i in range(1, len(nums)):
    for j in range(i):
        if nums[j] < nums[i]:
            dp[i] = max(dp[i], dp[j] + 1)

2. 2D DP

State depends on two indices — often for strings, grids, or two sequences.

# Unique Paths on an m×n grid
dp = [[1] * n for _ in range(m)]
for r in range(1, m):
    for c in range(1, n):
        dp[r][c] = dp[r-1][c] + dp[r][c-1]

3. Knapsack DP

Decide to include or exclude each item.

# 0/1 Knapsack: max value with weight capacity W
dp = [0] * (W + 1)
for weight, value in items:
    for w in range(W, weight - 1, -1):   # iterate backwards to avoid reuse
        dp[w] = max(dp[w], dp[w - weight] + value)

Practice Problems

Done	Question	Difficulty
	Counting Bits	Easy
	Decode Ways	Medium
	Unique Paths	Medium
	Longest Increasing Subsequence	Medium
	Word Break	Medium
	Maximal Square	Medium