动态规划的三种方法：⏫⏬💾
动态规划是一种用于解决复杂问题的算法。它通过将一个大问题分解为多个小问题，并把小问题的解保存下来，从而避免重复计算。本文将使用 Java 语言来讲解动态规划的三种方法：自顶向下（⏫）、自底向上（⏬）和备忘录（💾）。这些方法被广泛应用于很多问题中，比如背包🎒问题、最短路径🚶♂️问题和字符串匹配🔗问题。我们会用多个例子来解释这些方法的原理、时间复杂度⏱️和空间复杂度💾。这些方法各具特点，适合于不同类型的问题，在实际应用中也各有优势和劣势，合理选择合适的方法可以大大提高算法的效率📈。
1. 自顶向下（⏫ 递归 + 备忘录 💾）
自顶向下方法是一种递归🔄方法。从原问题开始，逐步分解为更小的问题，直到找到最简单的子问题。为了避免重复计算，我们使用备忘录💾来存储中间结果。这种方式可以加快速度，也更容易理解，尤其适合问题本身具有递归结构的场景。自顶向下方法的一个关键点在于其递归特性，它能够快速找到问题的解决路径，但如果递归深度过大，也可能会导致栈溢出。因此，备忘录是这个方法中不可缺少的部分，它确保每个子问题只被求解一次，从而显著减少了不必要的重复计算。
示例 1：斐波那契数列 🔢
问题描述：计算斐波那契数列的第 n 项。
斐波那契数列是经典的动态规划问题，定义为前两项是 0 和 1，从第三项开始每一项等于前两项之和。自顶向下的方式非常适合这个问题，因为它可以自然地通过递归来定义整个过程，同时使用备忘录💾来避免对相同子问题的重复求解。
import java.util.HashMap;public class FibonacciTopDown {private HashMap<Integer, Integer> memo = new HashMap<>();public int fib(int n) {if (n <= 1) return n;return memo.computeIfAbsent(n, key -> fib(key - 1) + fib(key - 2));}public static void main(String[] args) {FibonacciTopDown fibCalculator = new FibonacciTopDown();System.out.println(fibCalculator.fib(10)); // 输出 55}
}
在这个实现中，我们通过递归求解斐波那契数列，并将已经计算过的值存储在 HashMap 中，避免了重复的计算过程。
数据变化表格 📊
| n | 结果 |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
| 5 | 5 |
| 6 | 8 |
| 7 | 13 |
| 8 | 21 |
| 9 | 34 |
| 10 | 55 |
这种方式的优点在于直观、易于理解，尤其在处理递归性问题时非常简洁。但如果没有备忘录💾，递归会导致大量的重复计算，时间复杂度会从 O(n) 增加到指数级。
示例 2：背包问题 🎒
问题描述：给定一些物品的重量和价值，还有一个背包的容量，找到放入背包的物品组合，使得总价值最大。
背包问题也是经典的动态规划问题。在自顶向下方法中，我们可以把问题逐步分解为包含更少物品和更小容量的子问题。通过备忘录💾保存每个子问题的解，我们可以显著减少重复计算，从而提高算法效率📈。
import java.util.HashMap;public class KnapsackTopDown {private HashMap<String, Integer> memo = new HashMap<>();public int knapsack(int[] weights, int[] values, int capacity, int n) {if (n == 0 || capacity == 0) return 0;String key = n + "," + capacity;return memo.computeIfAbsent(key, k -> {if (weights[n - 1] > capacity) {return knapsack(weights, values, capacity, n - 1);} else {int include = values[n - 1] + knapsack(weights, values, capacity - weights[n - 1], n - 1);int exclude = knapsack(weights, values, capacity, n - 1);return Math.max(include, exclude);}});}public static void main(String[] args) {KnapsackTopDown solver = new KnapsackTopDown();int[] weights = {1, 2, 3, 8};int[] values = {10, 15, 40, 50};int capacity = 5;System.out.println(solver.knapsack(weights, values, capacity, weights.length)); // 输出 55}
}
在背包问题的自顶向下解决中，我们考虑每个物品是否放入背包，以及不同容量下的最优解，通过这种分解，问题被逐步解决。
数据变化表格 📊
| 物品编号 | 重量 ⚖️ | 价值 💰 | 当前容量 🎒 | 最大价值 💎 |
|---|---|---|---|---|
| 1 | 1 | 10 | 5 | 10 |
| 2 | 2 | 15 | 5 | 25 |
| 3 | 3 | 40 | 5 | 55 |
| 4 | 8 | 50 | 5 | 55 |
这种方式的优点是可以处理复杂的组合问题，通过递归实现分治，但递归深度较大时也容易导致性能问题。
示例 3：爬楼梯问题 🏃♂️
问题描述：你要爬 n 级台阶，每次可以爬 1 级或 2 级，问有多少种不同的方法可以到达楼顶。
这个问题也是一个典型的动态规划问题，可以通过递归解决并使用备忘录💾来保存中间结果。爬楼梯问题的递归定义非常简单，适合用自顶向下的方法进行解决。
import java.util.HashMap;public class ClimbStairsTopDown {private HashMap<Integer, Integer> memo = new HashMap<>();public int climbStairs(int n) {if (n <= 2) return n;return memo.computeIfAbsent(n, key -> climbStairs(key - 1) + climbStairs(key - 2));}public static void main(String[] args) {ClimbStairsTopDown solver = new ClimbStairsTopDown();System.out.println(solver.climbStairs(5)); // 输出 8}
}
数据变化表格 📊
| n | 方法数 🔢 |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 5 |
| 5 | 8 |
这种方法使得递归的层数减少，同时通过备忘录保存已经计算过的结果，避免了重复求解，极大提高了算法的效率📈。
原理
- 使用递归来解决原问题，不断将其分解为更小的子问题。
- 使用
HashMap💾 来存储每个子问题的结果，避免重复计算。 - 递归🔄加备忘录💾的结合使得算法既直观又高效，避免了指数级别的复杂度。
时间和空间复杂度
- 时间复杂度 ⏱️：O(n)，每个子问题只需要计算一次。
- 空间复杂度 💾：O(n)，需要存储中间结果和递归调用的栈空间。
2. 自底向上（⏬ 迭代）
自底向上是一种迭代的方法。它从最小的子问题开始，逐步构建到原问题的解。这种方法不需要递归调用，所以可以避免栈溢出问题。它通过一个数组来存储子问题的解，一步步推导出最终答案。相比于自顶向下，自底向上的方法更加适合于那些递归深度较大的问题，因为它可以有效地避免栈溢出的问题。
示例 1：斐波那契数列 🔢
问题描述：计算斐波那契数列的第 n 项。
通过自底向上的方式计算斐波那契数列的第 n 项，我们从最小的问题开始，一步一步向上计算，直到最终得到结果。这种方式通过迭代来替代递归，避免了递归栈溢出的问题。
public class FibonacciBottomUp {public int fib(int n) {if (n <= 1) return n;int prev1 = 0, prev2 = 1;for (int i = 2; i <= n; i++) {int current = prev1 + prev2;prev1 = prev2;prev2 = current;}return prev2;}public static void main(String[] args) {FibonacciBottomUp fibCalculator = new FibonacciBottomUp();System.out.println(fibCalculator.fib(10)); // 输出 55}
}
数据变化表格 📊
| i | prev1 | prev2 | current |
|---|---|---|---|
| 2 | 0 | 1 | 1 |
| 3 | 1 | 1 | 2 |
| 4 | 1 | 2 | 3 |
| 5 | 2 | 3 | 5 |
| 6 | 3 | 5 | 8 |
| 7 | 5 | 8 | 13 |
| 8 | 8 | 13 | 21 |
| 9 | 13 | 21 | 34 |
| 10 | 21 | 34 | 55 |
这种方法的好处在于其空间复杂度较低，只需要常数的空间来存储当前值和前两个值。
示例 2：背包问题 🎒
问题描述：给定一些物品的重量和价值，还有一个背包的容量，找到放入背包的物品组合，使得总价值最大。
通过自底向上的方法，我们使用一个数组来记录每种容量下的最优解，从最小的容量开始，逐步向上计算到最终的目标容量。
public class KnapsackBottomUp {public int knapsack(int[] weights, int[] values, int capacity) {int n = weights.length;int[] dp = new int[capacity + 1];for (int i = 0; i < n; i++) {for (int w = capacity; w >= weights[i]; w--) {dp[w] = Math.max(dp[w], values[i] + dp[w - weights[i]]);}}return dp[capacity];}public static void main(String[] args) {KnapsackBottomUp solver = new KnapsackBottomUp();int[] weights = {1, 2, 3, 8};int[] values = {10, 15, 40, 50};int capacity = 5;System.out.println(solver.knapsack(weights, values, capacity)); // 输出 55}
}
数据变化表格 📊
| 容量 🎒 | dp[容量] (更新过程) |
|---|---|
| 1 | 10 |
| 2 | 15 |
| 3 | 40 |
| 4 | 50 |
| 5 | 55 |
示例 3：爬楼梯问题 🏃♂️
问题描述：你要爬 n 级台阶，每次可以爬 1 级或 2 级，问有多少种不同的方法可以到达楼顶。
爬楼梯问题在自底向上的方法中，从最小的台阶数开始，逐步构建到最终的结果。
public class ClimbStairsBottomUp {public int climbStairs(int n) {if (n <= 2) return n;int prev1 = 1, prev2 = 2;for (int i = 3; i <= n; i++) {int current = prev1 + prev2;prev1 = prev2;prev2 = current;}return prev2;}public static void main(String[] args) {ClimbStairsBottomUp solver = new ClimbStairsBottomUp();System.out.println(solver.climbStairs(5)); // 输出 8}
}
数据变化表格 📊
| i | prev1 | prev2 | current |
|---|---|---|---|
| 3 | 1 | 2 | 3 |
| 4 | 2 | 3 | 5 |
| 5 | 3 | 5 | 8 |
原理
- 从最小的子问题开始计算，逐步向上构建到原问题。
- 不使用递归🔄，避免了递归带来的开销。
- 自底向上的方法适用于递归深度较大可能导致栈溢出的情况。
时间和空间复杂度
- 时间复杂度 ⏱️：O(n)，需要计算每个子问题。
- 空间复杂度 💾：O(1)，只需要常数个变量来存储结果。
3. 备忘录（Memoization 💾）
备忘录方法和自顶向下类似，通过递归解决问题，但在计算过程中用一个缓存来存储中间结果。这样可以减少重复计算，提高效率。备忘录的方法结合了递归的直观性和缓存技术的高效性，是解决很多复杂问题的有效手段。
示例：最小路径和 🛤️
问题描述：给定一个 m x n 的网格，每个位置有一个非负整数，找到从左上角到右下角的最小路径和。
import java.util.Arrays;public class MinPathSumMemo {private int[][] memo;public int minPathSum(int[][] grid) {int m = grid.length;int n = grid[0].length;memo = new int[m][n];for (int[] row : memo) {Arrays.fill(row, -1);}return dfs(grid, m - 1, n - 1);}private int dfs(int[][] grid, int i, int j) {if (i < 0 || j < 0) return Integer.MAX_VALUE;if (i == 0 && j == 0) return grid[0][0];if (memo[i][j] != -1) return memo[i][j];int left = dfs(grid, i, j - 1);int up = dfs(grid, i - 1, j);memo[i][j] = grid[i][j] + Math.min(left, up);return memo[i][j];}public static void main(String[] args) {MinPathSumMemo solver = new MinPathSumMemo();int[][] grid = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};System.out.println(solver.minPathSum(grid)); // 输出 7}
}
数据变化表格 📊
| i \ j | 0 | 1 | 2 |
|---|---|---|---|
| 0 | 1 | 4 | 5 |
| 1 | 2 | 7 | 6 |
| 2 | 6 | 8 | 7 |
原理
- 使用递归🔄来查找每个子问题的解，同时用数组💾记录每个位置的最小路径和。
- 避免对已经计算过的子问题重复求解。
- 结合了递归的易理解性和缓存技术的高效性。
时间和空间复杂度
- 时间复杂度 ⏱️：O(m * n)，每个位置只需要计算一次。
- 空间复杂度 💾：O(m * n)，用于存储每个位置的结果。
总结
| 方法 | 实现方式 | 时间复杂度 ⏱️ | 空间复杂度 💾 | 适用场景 |
|---|---|---|---|---|
| 自顶向下 | 递归 + 备忘录 | O(n) | O(n) | 递归易于理解的问题 |
| 自底向上 | 迭代 + 数组 | O(n) | O(1) | 递归深度过大时适用 |
| 自底向上优化 | 迭代 + 常量存储 | O(n) | O(1) | 需要优化空间时适用 |
| 备忘录 | 缓存递归中间结果 | O(m * n) | O(m * n) | 多维问题，减少重复计算 |
每种方法都有自己的优缺点。自顶向下的方法适合递归容易表达的问题，而自底向上适合需要避免深递归的问题。根据具体情况选择合适的方法，能够让问题的解决更加高效📈。掌握这三种动态规划的方法，并灵活使用它们，是解决复杂问题的重要技能🧠。