java算法动态规划

### Java 中动态规划算法的实现 动态规划是一种高效的优化技术，适用于解决具有重叠子问题和最优子结构性质的问题。以下是几个经典的动态规划问题及其对应的 Java 实现。 --- #### 1. **斐波那契数列** 斐波那契数列是一个典型的动态规划问题，可以通过自底向上的方式高效计算第 `n` 项的值。 ```java public class Fibonacci { public static int fib(int n) { if (n == 0) return 0; if (n == 1) return 1; int a = 0; // f(n-2) int b = 1; // f(n-1) int c = 0; // f(n) for (int i = 2; i <= n; i++) { c = a + b; // 当前状态由之前的状态决定 a = b; // 更新 f(n-2) b = c; // 更新 f(n-1) } return b; } public static void main(String[] args) { System.out.println(fib(5)); // 输出：5 } } ``` 此代码利用了滚动数组的思想，仅保留必要的中间结果，从而节省空间复杂度[^4]。 --- #### 2. **杨辉三角** 杨辉三角是另一个常见的动态规划应用场景。给定行号 `numRows`，返回其对应的所有行。 ```java import java.util.ArrayList; import java.util.List; public class YangHuiTriangle { public List<List<Integer>> generate(int numRows) { List<List<Integer>> result = new ArrayList<>(); if (numRows == 0) return result; for (int i = 0; i < numRows; i++) { List<Integer> row = new ArrayList<>(); for (int j = 0; j <= i; j++) { if (j == 0 || j == i) { row.add(1); } else { row.add(result.get(i - 1).get(j - 1) + result.get(i - 1).get(j)); } } result.add(row); } return result; } public static void main(String[] args) { YangHuiTriangle solution = new YangHuiTriangle(); System.out.println(solution.generate(5)); // 打印杨辉三角的前五行 } } ``` 该实现通过逐层构建每一行的结果，并基于之前的行推导当前行的内容[^2]。 --- #### 3. **最长递增子序列 (LIS)** 最长递增子序列问题是动态规划的经典应用之一。目标是从一个数组中找到长度最大的严格递增子序列。 ```java import java.util.Arrays; public class LongestIncreasingSubsequence { public int lengthOfLIS(int[] nums) { if (nums.length == 0) return 0; int[] dp = new int[nums.length]; Arrays.fill(dp, 1); for (int i = 1; i < nums.length; i++) { for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) { dp[i] = Math.max(dp[i], dp[j] + 1); // 状态转移方程 } } } int maxLength = 0; for (int value : dp) { maxLength = Math.max(maxLength, value); } return maxLength; } public static void main(String[] args) { LongestIncreasingSubsequence lis = new LongestIncreasingSubsequence(); int[] input = {10, 9, 2, 5, 3, 7, 101, 18}; System.out.println(lis.lengthOfLIS(input)); // 输出：4 } } ``` 在此代码中，`dp[i]` 表示以 `nums[i]` 结尾的最大递增子序列长度。最终答案为整个数组中的最大值[^1]。 --- #### 4. **剪绳子问题** 这是一个涉及最大化乘积的经典动态规划问题。假设有一根长度为 `n` 的绳子，将其切割成若干段并使每段长度的乘积最大化。 ```java public class CutRope { public static int cutByDP(int n) { if (n < 2) return 0; if (n == 2) return 1; if (n == 3) return 2; int[] products = new int[n + 1]; products[0] = 0; products[1] = 1; products[2] = 2; products[3] = 3; for (int i = 4; i <= n; i++) { int maxProduct = 0; for (int j = 1; j <= i / 2; j++) { maxProduct = Math.max(maxProduct, products[j] * products[i - j]); } products[i] = maxProduct; } return products[n]; } public static void main(String[] args) { System.out.println(cutByDP(8)); // 输出：18 } } ``` 这段代码展示了如何通过记录历史最佳解来逐步解决问题[^3]。 --- ### 总结 以上四个例子分别涵盖了不同的动态规划场景，包括线性表、二维矩阵以及组合最优化等问题。这些案例充分体现了动态规划的核心思想——分解问题、存储中间结果以避免重复计算。 ---