Introduction to Dynamic Programming

Introduction to Dynamic Programming

Dynamic programming (DP) is a technique for problems where a naive recursive solution solves the same subproblems over and over. Instead of recomputing them, you solve each distinct subproblem once, store its answer, and reuse it. That often turns exponential time into polynomial time.

DP has a reputation for being hard. The hard part isn't the technique itself, which is just "recursion plus a cache". It's defining the right subproblem. This lesson focuses on that skill.

When DP applies

Two properties must hold:

1. Optimal substructure: the answer to the problem can be built from answers to smaller instances of the same problem. The cheapest way to climb to step n comes from the cheapest ways to reach steps n−1 and n−2.
2. Overlapping subproblems: the recursion reaches the same smaller instances many times. If every subproblem were distinct, as in merge sort, caching would gain nothing. That's plain divide and conquer.

Typical signals in a problem statement: "count the number of ways", "minimum/maximum cost/length/profit", "is it possible to…", over sequences, grids or capacities where choices at each step affect the future.

Seeing the overlap: Fibonacci

int fib(int n) {                       // naive: O(2^n)
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

fib(5) calls fib(3) twice and fib(2) three times, and the duplication grows exponentially. There are only n + 1 distinct subproblems, though.

Top-down: memoization

Keep the recursive structure, and cache the results:

long fib(int n, long[] memo) {         // call with memo = new long[n + 1], filled with -1
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
}

Each state is computed once, so this is O(n) time. It uses long because fib(47) already overflows an int.

Bottom-up: tabulation

Fill a table from the smallest subproblems upward, so every dependency is ready before it's needed:

long fib(int n) {
    if (n <= 1) return n;
    long prev2 = 0, prev1 = 1;         // only the last two values are ever needed
    for (int i = 2; i <= n; i++) {
        long cur = prev1 + prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

That's O(n) time and O(1) space.

Both have the same complexity. Top-down is often easier to derive from the recurrence, and bottom-up is easier to optimize.

The four-step recipe

For any DP problem, write these down explicitly before writing code:

1. State: what does dp[i] (or dp[i][j]) mean, in words? Example: "dp[i] = the minimum cost to reach step i."
2. Transition: how is a state computed from smaller states? This is the recurrence, and it comes from asking "what's the last decision made?"
3. Base cases: the smallest states, whose answers are known directly.
4. Answer and order: which state holds the final answer, and in what order must states be computed?

Complexity is then (number of states) × (work per transition).

Worked example: Min Cost Climbing Stairs

1. State: dp[i] = the minimum cost to arrive at position i.
2. Transition: the last move came from i−1 or i−2: dp[i] = min(dp[i−1] + cost[i−1], dp[i−2] + cost[i−2]).
3. Base cases: dp[0] = dp[1] = 0 (you can start there for free).
4. Answer: dp[n], computed left to right.

int minCostClimbingStairs(int[] cost) {
    int n = cost.length;
    int twoBack = 0, oneBack = 0;                      // dp[i-2], dp[i-1]
    for (int i = 2; i <= n; i++) {
        int cur = Math.min(oneBack + cost[i - 1], twoBack + cost[i - 2]);
        twoBack = oneBack;
        oneBack = cur;
    }
    return oneBack;
}

That's O(n) time and O(1) space.

Worked example: House Robber, a choice at each step

• State: dp[i] = the best loot using houses 0..i.
• Last decision: either skip house i (dp[i−1]), or rob it and skip house i−1 (dp[i−2] + nums[i]).
• dp[i] = max(dp[i−1], dp[i−2] + nums[i]).

int rob(int[] nums) {
    int prev2 = 0, prev1 = 0;
    for (int x : nums) {
        int cur = Math.max(prev1, prev2 + x);
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

"Skip or take" choices like this are at the heart of the knapsack family (see 0/1 Knapsack Pattern).

Common DP families

Common mistakes

• A vague state. If you can't say in one sentence what dp[i] means, the transition will be wrong.
• A wrong fill order: reading a state that hasn't been computed yet.
• Forgetting base cases, or initializing min-problems with 0 instead of infinity.
• Integer overflow when counting ways. Use long, or apply the modulus the problem specifies.
• Using greedy when DP is needed. Coin change with coins {1, 3, 4} and amount 6: greedy picks 4+1+1 (3 coins), but 3+3 (2 coins) is optimal.

Follow-up questions this topic invites — and their answers

Q: How do you tell whether a problem needs DP or greedy? A: Greedy works when a locally best choice is provably part of some optimal solution (an exchange argument). If you can find a small counter-example where the locally best choice leads to a worse overall result, you need to consider all choices, which means DP.

Q: Memoization or tabulation: which should I use in an interview? A: Whichever you can write correctly fastest. Memoization is usually easiest to derive from the recurrence. Convert to tabulation if recursion depth could overflow the stack, or if the interviewer asks for space optimization.

Q: How do you reduce DP space? A: Look at which previous states the transition reads. If dp[i] only needs dp[i−1] and dp[i−2], keep two variables. If a 2-D row only needs the previous row, keep one or two rows.

Q: How do you reconstruct the actual solution, not just its value? A: Keep the full table (or a parent/choice array), then walk backwards from the answer state, following which transition produced each value.

Q: What's the time complexity of a DP solution? A: The number of distinct states multiplied by the cost of computing each one. For example, LCS has m × n states with O(1) work each, which is O(m·n).