动态规划：二维 DP 与背包问题

二维 DP 模板

dp[i][j] 一般表示在 i/j 定义的某种范围下的最优解。

最长公共子序列（LCS，LeetCode 1143）

int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            if (text1.charAt(i-1) == text2.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];
}

编辑距离（LeetCode 72）

int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i-1) == word2.charAt(j-1))
                dp[i][j] = dp[i-1][j-1];
            else
                dp[i][j] = 1 + Math.min(dp[i-1][j-1],      // 替换
                                Math.min(dp[i-1][j],         // 删除
                                         dp[i][j-1]));       // 插入
        }
    return dp[m][n];
}

0/1 背包

每件物品只能选一次，最大化价值：

// weights[i] 重量，values[i] 价值，capacity 总容量
int knapsack01(int[] weights, int[] values, int capacity) {
    int n = weights.length;
    int[] dp = new int[capacity + 1];  // 滚动数组优化（一维 dp）
    for (int i = 0; i < n; i++)
        for (int j = capacity; j >= weights[i]; j--)  // 逆序遍历（防止重复选）
            dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
    return dp[capacity];
}

分割等和子集（LeetCode 416）：0/1 背包变体

boolean canPartition(int[] nums) {
    int sum = Arrays.stream(nums).sum();
    if (sum % 2 != 0) return false;
    int target = sum / 2;
    boolean[] dp = new boolean[target + 1];
    dp[0] = true;
    for (int x : nums)
        for (int j = target; j >= x; j--)
            dp[j] |= dp[j - x];
    return dp[target];
}

完全背包

每件物品可选无限次：

int completeKnapsack(int[] weights, int[] values, int capacity) {
    int[] dp = new int[capacity + 1];
    for (int i = 0; i < weights.length; i++)
        for (int j = weights[i]; j <= capacity; j++)  // 正序遍历（允许重复选）
            dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
    return dp[capacity];
}

零钱兑换 II（LeetCode 518）：完全背包变体（组合数）

int change(int amount, int[] coins) {
    int[] dp = new int[amount + 1];
    dp[0] = 1;
    for (int coin : coins)
        for (int j = coin; j <= amount; j++)
            dp[j] += dp[j - coin];
    return dp[amount];
}

最小路径和（LeetCode 64）

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

区间 DP：戳气球（LeetCode 312）

int maxCoins(int[] nums) {
    int n = nums.length;
    int[] arr = new int[n + 2];  // 两端添加虚拟气球
    arr[0] = arr[n + 1] = 1;
    for (int i = 1; i <= n; i++) arr[i] = nums[i - 1];
    int[][] dp = new int[n + 2][n + 2];
    // i..j 范围内的最大金币，k 是最后一个戳破的气球
    for (int len = 1; len <= n; len++)
        for (int i = 1; i <= n - len + 1; i++) {
            int j = i + len - 1;
            for (int k = i; k <= j; k++)
                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];
}