16. Dynamic Programming

Dynamic programming (DP) is the hardest topic in DSA interviews. Not because the code is complex — most DP solutions are short. It's hard because recognizing that a problem is DP, defining the state, and finding the recurrence requires a mental shift. This lesson gives you the framework to identify and approach DP problems.

The Core Idea

DP solves problems by breaking them into overlapping subproblems and storing results so you never solve the same subproblem twice.

Fibonacci without DP:
fib(5) → fib(4) + fib(3)
         fib(3) + fib(2)   fib(2) + fib(1)
         fib(2) + fib(1)   ...

fib(3) is computed twice. fib(2) is computed three times.
Without caching: O(2ⁿ). With caching: O(n).

Two requirements for DP to apply:

1. Optimal substructure — the optimal solution contains optimal solutions to subproblems
2. Overlapping subproblems — the same subproblems are solved multiple times

If subproblems don't overlap, it's just divide-and-conquer (like merge sort). If there's no optimal substructure, DP won't help.

Memoization vs Tabulation

Two ways to implement DP:

Memoization (top-down) — recursive, cache results as you go. Start from the big problem, break down.

Fibonacci — memoization (explicit memo parameter):

func fib(n int, memo map[int]int) int {
    if n <= 1 {
        return n
    }
    if v, ok := memo[n]; ok {
        return v
    }
    memo[n] = fib(n-1, memo) + fib(n-2, memo)
    return memo[n]
}

Fibonacci — memoization with closure (cleaner call site):

func fib(n int) int {
    memo := map[int]int{}
    var solve func(int) int
    solve = func(n int) int {
        if n <= 1 {
            return n
        }
        if v, ok := memo[n]; ok {
            return v
        }
        memo[n] = solve(n-1) + solve(n-2)
        return memo[n]
    }
    return solve(n)
}

Tabulation (bottom-up) — iterative, fill a table from smallest subproblems up. No recursion.

// Fibonacci — tabulation
func fib(n int) int {
    if n <= 1 {
        return n
    }
    dp := make([]int, n+1)
    dp[0], dp[1] = 0, 1
    for i := 2; i <= n; i++ {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

Both are O(n) time, O(n) space. Tabulation is usually preferred — no recursion stack, easier to optimize space.

Space optimization — when you only need the last 1-2 values, drop the array:

// Fibonacci — O(1) space
func fib(n int) int {
    if n <= 1 {
        return n
    }
    prev, curr := 0, 1
    for i := 2; i <= n; i++ {
        prev, curr = curr, prev+curr
    }
    return curr
}

Memoization with Map

When the state has multiple parameters or non-integer keys, use a map for memoization. This is Go's standard pattern for top-down DP with complex state:

// Multi-parameter memoization using string key
// Example: grid paths with obstacles — memo keyed by "row,col"
func uniquePathsWithObstacles(grid [][]int) int {
    memo := map[string]int{}
    return dfs(grid, 0, 0, memo)
}

func dfs(grid [][]int, r, c int, memo map[string]int) int {
    if r >= len(grid) || c >= len(grid[0]) || grid[r][c] == 1 {
        return 0
    }
    if r == len(grid)-1 && c == len(grid[0])-1 {
        return 1
    }
    key := fmt.Sprintf("%d,%d", r, c)
    if v, ok := memo[key]; ok {
        return v
    }
    memo[key] = dfs(grid, r+1, c, memo) + dfs(grid, r, c+1, memo)
    return memo[key]
}

When to use map vs slice for memo:

• Use []int or [][]int when state is small consecutive integers (most 1D/2D problems)
• Use map[string]int when state is multi-dimensional, sparse, or includes non-integer keys
• Use a struct key (map[[2]int]int) for fixed-size tuple keys — avoids string formatting cost

Memoization (Top-Down) vs Tabulation (Bottom-Up)

Rule of thumb: Start with memoization to get a working solution, then convert to tabulation for performance. In interviews, either is fine — pick whichever you can write faster.

The DP Framework

Every DP problem follows this pattern:

1. Define the state — what does dp[i] (or dp[i][j]) represent?
2. Find the recurrence — how does dp[i] relate to smaller subproblems?
3. Set base cases — what are the trivial answers?
4. Determine the order — fill the table so dependencies are already computed
5. Extract the answer — usually dp[n] or dp[n][m]

Classic Example: Climbing Stairs

LeetCode 70 - Climbing Stairs

You can climb 1 or 2 steps at a time. How many ways to reach step n?

// State: dp[i] = number of ways to reach step i
// Recurrence: dp[i] = dp[i-1] + dp[i-2]
// Base: dp[0] = 1, dp[1] = 1
func climbStairs(n int) int {
    if n <= 1 {
        return 1
    }
    prev, curr := 1, 1
    for i := 2; i <= n; i++ {
        prev, curr = curr, prev+curr
    }
    return curr
}

This is literally Fibonacci. Many DP problems reduce to known patterns once you define the state correctly.

Classic Example: Coin Change

Given coins of different denominations, find the minimum number of coins to make a target amount.

LeetCode 322 - Coin Change

// State: dp[i] = min coins to make amount i
// Recurrence: dp[i] = min(dp[i-coin] + 1) for each coin
// Base: dp[0] = 0
func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
    for i := range dp {
        dp[i] = amount + 1 // impossible sentinel
    }
    dp[0] = 0

    for i := 1; i <= amount; i++ {
        for _, coin := range coins {
            if coin <= i && dp[i-coin]+1 < dp[i] {
                dp[i] = dp[i-coin] + 1
            }
        }
    }
    if dp[amount] > amount {
        return -1
    }
    return dp[amount]
}

Common DP Categories

Knapsack: 0/1 vs Unbounded

The knapsack pattern has two variants that look similar but differ in one critical way:

0/1 Knapsack — each item can be used at most once. Iterate capacity right-to-left so you don't reuse items.

LeetCode 416 - Partition Equal Subset Sum

// Can we make target sum using each number at most once?
func canPartition(nums []int, target int) bool {
    dp := make([]bool, target+1)
    dp[0] = true
    for _, num := range nums {
        for j := target; j >= num; j-- { // RIGHT to LEFT
            dp[j] = dp[j] || dp[j-num]
        }
    }
    return dp[target]
}

Unbounded Knapsack — each item can be used unlimited times. Iterate left-to-right so items can be reused.

// Coin change — each coin can be used unlimited times
for i := 1; i <= amount; i++ {
    for _, coin := range coins {
        if coin <= i {
            dp[i] = min(dp[i], dp[i-coin]+1) // LEFT to RIGHT
        }
    }
}

The direction matters: right-to-left uses the previous row's values (item not yet used). Left-to-right uses the current row's values (item already available for reuse).

2D Grid DP

Grid problems where you can only move right or down. Each cell depends on the cell above and to the left.

LeetCode 62 - Unique Paths

// Unique paths from top-left to bottom-right
func uniquePaths(m, n int) int {
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
        dp[i][0] = 1 // only one way to reach any cell in first column
    }
    for j := 0; j < n; j++ {
        dp[0][j] = 1 // only one way to reach any cell in first row
    }
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[i][j] = dp[i-1][j] + dp[i][j-1] // from above + from left
        }
    }
    return dp[m-1][n-1]
}

The pattern: dp[i][j] depends on dp[i-1][j] (above) and dp[i][j-1] (left). First row and first column are base cases.

String DP: LCS and Edit Distance

Longest Common Subsequence (LCS) — find the longest sequence that appears in both strings (not necessarily contiguous).

LeetCode 1143 - Longest Common Subsequence

func longestCommonSubsequence(s1, s2 string) int {
    m, n := len(s1), len(s2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if s1[i-1] == s2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1 // characters match
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]) // skip one
            }
        }
    }
    return dp[m][n]
}

Edit Distance — minimum insertions, deletions, and replacements to transform one string into another.

LeetCode 72 - Edit Distance

func minDistance(word1, word2 string) int {
    m, n := len(word1), len(word2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
        dp[i][0] = i // delete all characters
    }
    for j := 0; j <= n; j++ {
        dp[0][j] = j // insert all characters
    }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if word1[i-1] == word2[j-1] {
                dp[i][j] = dp[i-1][j-1] // no edit needed
            } else {
                dp[i][j] = 1 + min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]))
                //              replace          delete        insert
            }
        }
    }
    return dp[m][n]
}

Both follow the same structure: dp[i][j] represents the answer for s1[0..i-1] and s2[0..j-1]. If characters match, take the diagonal. If not, try all options and pick the best.

Space Optimization

Many 2D DP problems only look at the current row and the previous row. You can reduce O(m×n) space to O(n) using a rolling array:

// LCS with O(n) space instead of O(m×n)
func lcs(s1, s2 string) int {
    m, n := len(s1), len(s2)
    prev := make([]int, n+1)
    curr := make([]int, n+1)
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if s1[i-1] == s2[j-1] {
                curr[j] = prev[j-1] + 1
            } else {
                curr[j] = max(prev[j], curr[j-1])
            }
        }
        prev, curr = curr, make([]int, n+1)
    }
    return prev[n]
}

The rule: if dp[i] only depends on dp[i-1], keep two rows. If it only depends on earlier values in the same row, one row suffices (like knapsack).

How to Recognize DP

Look for these signals:

• "Count the number of ways" → likely DP
• "Find the minimum/maximum" with choices at each step → likely DP
• "Can you reach / is it possible" with overlapping paths → likely DP
• Problem has optimal substructure (best solution uses best sub-solutions)
• Brute force would try all combinations (exponential)

Not DP if:

• Greedy works (each local choice is globally optimal)
• No overlapping subproblems (divide-and-conquer instead)
• The problem is about a single traversal or scan

DP vs Greedy

If greedy works, use it — it's faster. DP is the fallback when greedy doesn't guarantee optimality.

Practice Problems

Key Takeaways

• DP = overlapping subproblems + optimal substructure — cache results to avoid recomputation
• Memoization (top-down, recursive) vs tabulation (bottom-up, iterative) — same complexity, tabulation usually preferred
• The framework: define state → find recurrence → set base cases → fill table → extract answer
• Common patterns: 1D linear, knapsack, 2D grid, strings, intervals
• "Count ways," "find min/max with choices," "is it possible" → think DP
• If greedy works, prefer it over DP — DP is the fallback for when local choices aren't globally optimal
• Space optimization: if dp[i] only depends on dp[i-1] (or dp[i-1] and dp[i-2]), use variables instead of an array