Dynamic Programming: 2D DP and Knapsack Systems

2D DP Foundations

In 2D Dynamic Programming, dp[i][j] typically represents the optimal solution within a range defined by two variables (e.g., indices of two strings, rows and columns of a matrix, or start and end of an interval).

Longest Common Subsequence (LCS: LeetCode 1143)

Classic sequence alignment problem.

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];
}

0/1 Knapsack (Optimized to 1D)

Each item can be picked at most once.

// weights[i] weight, values[i] value, capacity total
public int knapsack01(int[] w, int[] v, int capacity) {
    int[] dp = new int[capacity + 1];
    for (int i = 0; i < w.length; i++) {
        // Reverse iteration to prevent picking the same item multiple times
        for (int j = capacity; j >= w[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    return dp[capacity];
}

Complete Knapsack (Optimized to 1D)

Items can be picked infinitely often.

public int completeKnapsack(int[] w, int[] v, int capacity) {
    int[] dp = new int[capacity + 1];
    for (int i = 0; i < w.length; i++) {
        // Forward iteration allows picking the same item again
        for (int j = w[i]; j <= capacity; j++) {
            dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    return dp[capacity];
}

Minimum Path Sum (LeetCode 64)

Finding the minimum cost to reach the bottom-right of a matrix with space optimization.

public int minPathSum(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[] dp = new int[n];
    dp[0] = grid[0][0];
    for (int j = 1; j < n; j++) dp[j] = dp[j - 1] + grid[0][j];
    
    for (int i = 1; i < m; i++) {
        dp[0] += grid[i][0];
        for (int j = 1; j < n; j++) {
            dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
        }
    }
    return dp[n - 1];
}

Interval DP: Burst Balloons (LeetCode 312)

Solving based on the last balloon remaining.

public int maxCoins(int[] nums) {
    int n = nums.length;
    int[] arr = new int[n + 2];
    arr[0] = arr[n + 1] = 1;
    System.arraycopy(nums, 0, arr, 1, n);
    
    int[][] dp = new int[n + 2][n + 2];
    for (int length = 1; length <= n; length++) {
        for (int i = 1; i <= n - length + 1; i++) {
            int j = i + length - 1;
            for (int k = i; k <= j; k++) {
                // k is the last balloon to burst in range [i, j]
                dp[i][j] = Math.max(dp[i][j], 
                    arr[i - 1] * arr[k] * arr[j + 1] + dp[i][k - 1] + dp[k + 1][j]);
            }
        }
    }
    return dp[1][n];
}

筋