Introduction to Dynamic Programming

What is Dynamic Programming?

Dynamic Programming (DP) is a method for solving optimization problems by breaking them down into overlapping subproblems.

Two defining characteristics of DP:

1. Optimal Substructure: The optimal solution to a large problem can be constructed from the optimal solutions to its smaller subproblems.
2. Overlapping Subproblems: The same subproblems are solved multiple times during a naive recursive approach.

DP vs. Divide & Conquer: In Divide & Conquer (e.g., Merge Sort), subproblems are independent. In DP (e.g., Fibonacci), subproblems overlap and share results.

Evolution: From Recursion to DP

Using the Fibonacci sequence as a case study:

1. Brute-Force Recursion ($O(2^N)$)

int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2); // Massive redundant calculation
}

In the recursion tree for fib(5), fib(3) is computed twice, and fib(2) is computed three times.

2. Memoization (Top-Down DP - $O(N)$)

int[] memo;
int fib(int n) {
    memo = new int[n + 1];
    Arrays.fill(memo, -1);
    return helper(n);
}

int helper(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n]; // Cache hit
    memo[n] = helper(n - 1) + helper(n - 2);
    return memo[n];
}

3. Iteration (Bottom-Up DP - $O(N)$)

int fib(int n) {
    if (n <= 1) return n;
    int[] dp = new int[n + 1];
    dp[0] = 0; dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

4. Space Optimization ($O(1)$)

int fib(int n) {
    if (n <= 1) return n;
    int prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
        int next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

The DP Problem-Solving Checklist

1. Define the State: What exactly does dp[i] or dp[i][j] represent?
2. Derive the Transition Equation: How do we use previous results to calculate the current state?
3. Initialize Base Cases: What is the solution for the smallest possible input?
4. Determine Iteration Order: Ensure dependency directions (e.g., left-to-right, top-to-bottom) are respected.

Classic Example: Climbing Stairs (LeetCode 70)

Goal: Reach the $n$-th step by taking either 1 or 2 steps at a time.

• State: dp[i] = Number of distinct ways to reach step i.
• Transition: The last move was either from step i-1 or i-2.
  • $dp[i] = dp[i-1] + dp[i-2]$
• Initialization: dp[1] = 1, dp[2] = 2.

int climbStairs(int n) {
    if (n <= 2) return n;
    int a = 1, b = 2;
    for (int i = 3; i <= n; i++) {
        int temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

Classic Example: 0/1 Knapsack

Goal: Pick items with weight w[i] and value v[i] for a bag of capacity W to maximize total value. Each item used once.

• State: dp[j] = Max value for capacity j.
• Logic: For each item, decide to keep it or leave it.

int knapsack(int[] weights, int[] values, int capacity) {
    int[] dp = new int[capacity + 1];
    for (int i = 0; i < weights.length; i++) {
        // Iterate BACKWARDS to prevent using the SAME item multiple times in one row
        for (int j = capacity; j >= weights[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

Common DP Paradigms

Summary Summary

The "Thinking" of DP:

1. Identify the problem type: Is it asking for "Total ways," "Min/Max optimal," or "Feasibility"? Does it have overlapping work?
2. Define State: This is the single most important step. Don't move on until you can define dp[i] precisely.
3. State Transition: Look at the "Last Step." How did we get to state $i$?
4. Initialize: Secure the base cases.
5. Calculate Flow: Pick the iterative approach (Bottom-Up) for better efficiency and less boilerplate. 筋| Space Tune: If you only need results from the immediate previous state, compress the array into variables.