当前位置：首页 > news >正文

算法-动态规划

news 2025/7/19 6:57:48

下面是使用 Java 实现动态规划（Dynamic Programming） 解决以下经典 DP 问题 的完整代码和说明：

✅ 1. 0-1 背包问题（Knapsack Problem）

问题描述：

给定 n 个物品，每个物品有重量 weights[i] 和价值 values[i]，一个容量为 capacity 的背包。每个物品只能选一次，求能装入背包的最大总价值。

Java 实现：

public class Knapsack {public static int knapsack(int[] values, int[] weights, int capacity) {int n = values.length;int[][] dp = new int[n + 1][capacity + 1];for (int i = 1; i <= n; i++) {for (int w = 0; w <= capacity; w++) {if (weights[i - 1] <= w) {dp[i][w] = Math.max(dp[i - 1][w],dp[i - 1][w - weights[i - 1]] + values[i - 1]);} else {dp[i][w] = dp[i - 1][w];}}}return dp[n][capacity];}public static void main(String[] args) {int[] values = {60, 100, 120};int[] weights = {10, 20, 30};int capacity = 50;System.out.println(knapsack(values, weights, capacity)); // 输出 220}
}

✅ 2. 最长公共子序列（Longest Common Subsequence, LCS）

问题描述：

给定两个字符串 s1 和 s2，找出它们的最长公共子序列（不连续，但顺序一致）。

Java 实现：

public class LCS {public static int longestCommonSubsequence(String s1, String s2) {int m = s1.length();int 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];}public static void main(String[] args) {String s1 = "abcde";String s2 = "ace";System.out.println(longestCommonSubsequence(s1, s2)); // 输出 3}
}

✅ 3. 最长递增子序列（Longest Increasing Subsequence, LIS）

问题描述：

给定一个整数数组，找出其中 最长递增子序列 的长度（子序列元素顺序不变，但可以不连续）。

Java 实现：

public class LIS {public static int lengthOfLIS(int[] nums) {int n = nums.length;int[] dp = new int[n];int maxLen = 0;for (int i = 0; i < n; i++) {dp[i] = 1;for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) {dp[i] = Math.max(dp[i], dp[j] + 1);}}maxLen = Math.max(maxLen, dp[i]);}return maxLen;}public static void main(String[] args) {int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};System.out.println(lengthOfLIS(nums)); // 输出 4（序列：2, 3, 7, 101）}
}

✅ 4. 编辑距离（Edit Distance）

问题描述：

给定两个字符串 word1 和 word2，求将 word1 转换为 word2 所需的最少操作次数。操作包括：插入、删除、替换。

Java 实现：

public class EditDistance {public static int minDistance(String word1, String word2) {int m = word1.length();int 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(Math.min(dp[i - 1][j], dp[i][j - 1]),dp[i - 1][j - 1]);}}}return dp[m][n];}public static void main(String[] args) {String word1 = "horse";String word2 = "ros";System.out.println(minDistance(word1, word2)); // 输出 3}
}

✅ 5. 矩阵链乘法（Matrix Chain Multiplication）

问题描述：

给定一个矩阵链 p[0..n]，其中第 i 个矩阵的维度为 p[i-1] x p[i]，求矩阵相乘所需的最小乘法次数。

Java 实现：

public class MatrixChainMultiplication {public static int matrixChainOrder(int[] p) {int n = p.length - 1;int[][] dp = new int[n][n];for (int l = 2; l <= n; l++) { // 链长for (int i = 0; i < n - l + 1; i++) {int j = i + l - 1;dp[i][j] = Integer.MAX_VALUE;for (int k = i; k < j; k++) {int cost = dp[i][k] + dp[k + 1][j] + p[i] * p[k] * p[j];dp[i][j] = Math.min(dp[i][j], cost);}}}return dp[0][n - 1];}public static void main(String[] args) {int[] p = {1, 2, 3, 4}; // 矩阵维度：1x2, 2x3, 3x4System.out.println(matrixChainOrder(p)); // 输出 18}
}

✅ 总结对比表

问题	时间复杂度	空间复杂度	核心思想
背包问题	O(n * capacity)	O(n * capacity)	选或不选
LCS	O(m * n)	O(m * n)	末尾字符匹配
LIS	O(n²)	O(n)	逐个比较前面元素
编辑距离	O(m * n)	O(m * n)	插入/删除/替换
矩阵链乘法	O(n³)	O(n²)	分割点枚举