Dynamic Programming: State Definition, Transition, and Space Selection

The Essence of Dynamic Programming

Dynamic Programming (DP) is applicable to problems that exhibit Overlapping Subproblems and Optimal Substructure.

DP = Recursion + Memoization (Top-Down)
DP = Iterative Table Filling (Bottom-Up)

Comparison with Divide & Conquer: In DP, subproblems overlap and their results are cached for reuse. In Divide & Conquer, subproblems are mutually independent.

The Four-Step DP Process

1. Define the State: Determine the exact meaning of dp[i] or dp[i][j].
2. Derive the Transition Equation: Find how a large problem derives from smaller solved subproblems.
3. Establish Base Cases: Initialize the starting values (e.g., dp[0]).
4. Determine Order of Evaluation: Populate the table in an order that ensures dependencies are solved before their dependents.

Linear DP

Longest Increasing Subsequence (LIS)

// O(N^2) - Classic DP
// dp[i] = Length of LIS ending at index i
public int lengthOfLIS(int[] nums) {
    int n = nums.length, maxLen = 1;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxLen = Math.max(maxLen, dp[i]);
    }
    return maxLen;
}

Maximum Subarray Sum (Kadane's Algorithm)

// dp[i] = Maximum subarray sum ending at index i
// Transition: dp[i] = nums[i] + max(dp[i-1], 0)
public int maxSubArray(int[] nums) {
    int currentDP = nums[0], globalMax = nums[0];
    for (int i = 1; i < nums.length; i++) {
        currentDP = nums[i] + Math.max(currentDP, 0);
        globalMax = Math.max(globalMax, currentDP);
    }
    return globalMax;
}

2D DP

Longest Common Subsequence (LCS)

// dp[i][j] = Length of LCS for s1[0..i-1] and s2[0..j-1]
public int longestCommonSubsequence(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

Knapsack Problems

0-1 Knapsack (Finite items)

// dp[j] = Max value for capacity j
// Must iterate backwards to ensure each item is used ONLY once
public int knapsack01(int[] w, int[] v, int W) {
    int[] dp = new int[W + 1];
    for (int i = 0; i < w.length; i++) {
        for (int j = W; j >= w[i]; j--) { // BACKWARDS iteration
            dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    return dp[W];
}

Complete Knapsack (Infinite items)

// Iterate forwards to allow item reuse
public int completeKnapsack(int[] w, int[] v, int W) {
    int[] dp = new int[W + 1];
    for (int i = 0; i < w.length; i++) {
        for (int j = w[i]; j <= W; j++) { // FORWARDS iteration
            dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    return dp[W];
}

Interval DP

Burst Balloons (LeetCode 312)

$dp[i][j]$ is the maximum coins obtained by bursting all balloons between indices $i$ and $j$. We iterate based on the last balloon to be burst.

public int maxCoins(int[] nums) {
    int n = nums.length;
    int[] val = new int[n + 2];
    val[0] = val[n + 1] = 1;
    System.arraycopy(nums, 0, val, 1, n);
    
    int[][] dp = new int[n + 2][n + 2];
    for (int len = 2; len <= n + 1; len++) {
        for (int i = 0; i <= n + 1 - len; i++) {
            int j = i + len;
            for (int k = i + 1; k < j; k++) {
                dp[i][j] = Math.max(dp[i][j], 
                    dp[i][k] + val[i] * val[k] * val[j] + dp[k][j]);
            }
        }
    }
    return dp[0][n + 1];
}

Space Compression Techniques

Common Pitfalls

1. Ambiguous States: Ensure you can describe exactly what your dp index represents in plain English.
2. Missing Base Cases: Forgetting to initialize dp[0] correctly leads to offset or incorrect values.
3. Iteration Direction: 0-1 Knapsack requires reversed inner loops; Complete Knapsack requires forward.
4. Off-by-one results: Double-check if the result is in dp[n] or if you need to return the maximum value found across the entire array.

High-Frequency Optimization Patterns