动态规划：背包问题和最长公共子序列的Java实现

0-1背包问题

问题：N个物品，每个物品重量w[i]、价值v[i]，背包容量W，求能装入的最大价值。

状态定义：dp[i][j] = 前i个物品，容量j的最大价值

转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

public class Knapsack {
    // 二维DP
    public int knapsack(int W, int[] w, int[] v) {
        int n = w.length;
        int[][] dp = new int[n + 1][W + 1];
        
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= W; j++) {
                if (j >= w[i-1]) {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j - w[i-1]] + v[i-1]);
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[n][W];
    }
    
    // 空间优化（一维数组，逆序遍历）
    public int knapsackOptimized(int W, int[] w, int[] v) {
        int[] dp = new int[W + 1];
        for (int i = 0; i < w.length; i++) {
            // 逆序保证每个物品只取一次
            for (int j = W; j >= w[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
            }
        }
        return dp[W];
    }
}

最长公共子序列（LCS）

问题：求两个字符串的最长公共子序列（不要求连续）。

状态定义：dp[i][j] = text1[0..i-1]和text2[0..j-1]的LCS长度

转移方程：

• text1[i-1] == text2[j-1]：dp[i][j] = dp[i-1][j-1] + 1
• 否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

public class LCS {
    public 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];
    }
    
    // 回溯：还原LCS字符串
    public String backtrack(String text1, String text2, int[][] dp) {
        int i = text1.length(), j = text2.length();
        StringBuilder sb = new StringBuilder();
        while (i > 0 && j > 0) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                sb.append(text1.charAt(i - 1));
                i--; j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }
        return sb.reverse().toString();
    }
}

DP核心思想

概念	说明	背包问题	LCS
最优子结构	子问题最优解构成全局最优	容量W的最佳选择包含容量W-w[i]的最佳选择	text1[0..i]和text2[0..j]的LCS由更短的子串LCS组成
重叠子问题	子问题被重复计算	dp[i-1][j]被多次使用	dp[i-1][j]和dp[i][j-1]被多次计算
无后效性	子问题的解不影响其他子问题的解	已确定的前i个物品不影响后续选择	已匹配的前缀不影响后续匹配