Dynamic Programming Basics

Why this module exists

Dynamic programming is the most feared topic in coding interviews — but it shouldn't be. At its core, DP is just smart recursion: instead of recomputing the same subproblem many times, you store the result and reuse it.

This module builds your DP intuition through three classic problems that appear everywhere: Climbing Stairs (Fibonacci-style), House Robber (decision at each step), and Coin Change (minimization with choices).

1) The Two Properties of DP

A problem is a good fit for DP when it has:

Overlapping Subproblems The same smaller problem gets solved multiple times. In Fibonacci, fib(3) is computed when calculating both fib(5) and fib(4).

Optimal Substructure The optimal solution to the whole problem can be built from optimal solutions to subproblems. If the best way to climb 10 stairs uses the best way to climb 8 stairs, you have optimal substructure.

If a problem has both, DP will likely help.

2) Top-Down vs Bottom-Up

There are two ways to implement DP:

Top-Down (Memoization)

Start from the big problem, recurse down, cache results.

memo := make(map[int]int)

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

Bottom-Up (Tabulation)

Start from base cases, build up iteratively.

func climbStairs(n int) int {
    if n <= 2 {
        return n
    }
    dp := make([]int, n+1)
    dp[1], dp[2] = 1, 2
    for i := 3; i <= n; i++ {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

Which to use?

• Top-down is often easier to write (natural recursion)
• Bottom-up avoids recursion stack limits and is usually faster
• For interviews, either is fine — pick what you're comfortable with

3) The DP Recipe

When you suspect a problem needs DP:

1. Define the state: What does dp[i] represent?
   • Climbing Stairs: dp[i] = ways to reach step i
   • House Robber: dp[i] = max money robbing houses 0..i
   • Coin Change: dp[a] = min coins to make amount a
2. Find the recurrence: How does dp[i] relate to previous states?
   • Climbing: dp[i] = dp[i-1] + dp[i-2]
   • Robber: dp[i] = max(dp[i-1], dp[i-2] + nums[i])
   • Coins: dp[a] = min(dp[a-c] + 1) for each coin c
3. Identify base cases: What are the trivial answers?
   • Climbing: dp[1] = 1, dp[2] = 2
   • Robber: dp[0] = nums[0]
   • Coins: dp[0] = 0 (zero coins for zero amount)
4. Determine iteration order: Fill the table so dependencies are ready.

4) Space Optimization: Rolling Variables

Many DP solutions only need the last 1-2 states. Instead of storing the whole table, keep just what you need:

// Full table: O(n) space
dp := make([]int, n+1)
for i := 3; i <= n; i++ {
    dp[i] = dp[i-1] + dp[i-2]
}

// Rolling variables: O(1) space
prev, curr := 1, 2
for i := 3; i <= n; i++ {
    prev, curr = curr, prev+curr
}

This is called state compression or rolling array. Use it when:

• dp[i] only depends on a fixed number of previous states
• You want to optimize memory (large n)

5) Minimization DP Pattern

For problems asking "minimum X to achieve Y":

1. Initialize with infinity (or a large sentinel like amount + 1)
2. Base case is usually dp[0] = 0
3. Relax: dp[i] = min(dp[i], dp[i-cost] + 1)
4. If dp[target] is still infinity, return -1 (impossible)

func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
    for i := range dp {
        dp[i] = amount + 1 // sentinel for "impossible"
    }
    dp[0] = 0

    for a := 1; a <= amount; a++ {
        for _, c := range coins {
            if c <= a && dp[a-c]+1 < dp[a] {
                dp[a] = dp[a-c] + 1
            }
        }
    }

    if dp[amount] > amount {
        return -1
    }
    return dp[amount]
}

6) Common Mistakes

• Wrong base case: Off-by-one errors are rampant. Trace through with n=0, n=1.
• Wrong iteration order: If dp[i] needs dp[i+1], iterate backwards.
• Forgetting to handle impossible cases: Return -1 or check for sentinel.
• Using recursion without memoization: That's just exponential brute force.

7) Complexity Analysis

4) Longest Increasing Subsequence (LIS)

Classic DP with two levels:

• O(n²): dp[i] = 1 + max(dp[j]) for all j < i with nums[j] < nums[i]
• O(n log n): maintain tails where tails[k] is the smallest tail of any length k+1 subsequence

The optimized approach uses binary search to keep tails minimal and extendable.

Outcomes

After this module, you should be able to:

• Identify when a problem has overlapping subproblems
• Formulate a recurrence relation from the problem statement
• Implement both top-down and bottom-up solutions
• Optimize space using rolling variables
• Handle minimization DP with infinity initialization

Practice Set

1. Climbing Stairs (Easy) — Pure Fibonacci structure
2. House Robber (Medium) — Decision at each step: take or skip
3. Coin Change (Medium) — Minimization with multiple choices
4. Longest Increasing Subsequence (Medium) — DP + binary search optimization

Start with Climbing Stairs to get the recurrence pattern, then House Robber adds the "rob or skip" decision, and finally Coin Change introduces minimization with a loop over choices.