Introduction to Dynamic Programming

Introduction to Dynamic Programming

Dynamic Programming (DP) solves problems by breaking them into overlapping subproblems, solving each once, and storing the results. It applies when a problem has:

1. Optimal substructure: an optimal solution can be built from optimal solutions to subproblems
2. Overlapping subproblems: the same subproblems are solved repeatedly

The Classic Example: Fibonacci

// Naive recursion: O(2^n) — computes fib(3) many times
int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

// Top-down DP (memoization): O(n)
int[] memo = new int[n+1];
Arrays.fill(memo, -1);
int fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fib(n-1) + fib(n-2);
}

// Bottom-up DP (tabulation): O(n) time, O(1) space
int fib(int n) {
    if (n <= 1) return n;
    int prev2 = 0, prev1 = 1;
    for (int i = 2; i <= n; i++) {
        int curr = prev1 + prev2;
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

Top-Down vs Bottom-Up

The DP Framework

For any DP problem, answer these 4 questions:

1. State: What information do I need to describe a subproblem? dp[i], dp[i][j], dp[i][j][k]
2. Transition: How do I compute dp[i] from smaller subproblems?
3. Base case: What are the trivially known values?
4. Answer: Which cell(s) in the dp table hold the final answer?

House Robber (1D DP)

// State: dp[i] = max money robbing houses 0..i
// Transition: dp[i] = max(dp[i-1], dp[i-2] + nums[i])
// Base: dp[0] = nums[0], dp[1] = max(nums[0], nums[1])

public int rob(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];
    int prev2 = nums[0];
    int prev1 = Math.max(nums[0], nums[1]);
    for (int i = 2; i < n; i++) {
        int curr = Math.max(prev1, prev2 + nums[i]);
        prev2 = prev1;
        prev1 = curr;
    }
    return prev1;
}

Identifying DP Problems

DP is the right choice when:

• Problem asks for min/max/count of something
• Decision at each step affects future decisions
• Brute force is exponential (2^n or n!)
• You can define a recurrence relation

Common DP categories:

• Linear DP: dp[i] depends on previous cells
• 2D DP: dp[i][j] for matrix or two-string problems
• Interval DP: dp[i][j] means answer for subarray [i..j]
• Knapsack: item selection with constraints
• State machine: tracks mode/state transitions

Interview Tips

1. Start with brute force recursion → add memoization → convert to bottom-up if needed.
2. The hardest part is defining the state — once you have that, the transition usually follows naturally.
3. Space optimization: when dp[i] only depends on dp[i-1] and dp[i-2], you can use two variables instead of an array.