《剑指 Offer（第 2 版）》中，动态规划（Dynamic Programming, DP）和记忆化搜索（Memoization）是两种常见的算法技巧，常用于求解最优化问题。动态规划通过将问题分解为子问题，并存储中间结果来避免重复计算，而记忆化搜索是在递归的基础上，通过缓存已经计算过的结果来提高效率。
在这里，我将通过几个经典的 动态规划 和 记忆化搜索 问题，详细说明如何运用这些技巧来解决问题。
1. 动态规划与记忆化搜索的区别
- 动态规划（DP） 是一种自底向上的方法。通过从小到大的方式迭代计算子问题的解，最终得到整个问题的解。通常使用数组或表格存储中间结果。
- 记忆化搜索（Memoization） 是一种自顶向下的递归方法。通过递归求解问题的同时，将已经计算过的子问题的结果保存起来，避免重复计算。通常使用哈希表或数组缓存计算结果。
2. 示例问题：爬楼梯问题
问题描述：
有一个楼梯，总共有 n 阶，每次可以选择爬 1 或 2 阶，求爬到第 n 阶有多少种方法。
动态规划解法：
我们可以通过状态转移方程来求解这个问题：
- 设
dp[i]表示到达第i阶楼梯的方法数。 - 显然，
dp[i] = dp[i-1] + dp[i-2]，即到达第i阶的方法可以由到达第i-1阶和第i-2阶的方法推导出来。
代码实现：
#include <stdio.h>
int climbStairs(int n) {
if (n == 1) return 1;
int dp[n + 1]; // dp[i]表示爬到第i阶的方法数
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
int main() {
int n = 5;
printf("Ways to climb %d stairs: %d\n", n, climbStairs(n)); // 输出: 8
return 0;
}
动态规划分析：
- 时间复杂度：
O(n)，我们只需要遍历一次楼梯的每一阶。 - 空间复杂度：
O(n)，存储所有阶数的方法数。
3. 记忆化搜索解法：
记忆化搜索是递归的方式，每次递归时记录已经计算过的子问题的解，从而避免重复计算。
代码实现：
#include <stdio.h>
int memo[100]; // 使用数组作为备忘录
int climbStairsMemo(int n) {
if (n == 1) return 1;
if (n == 2) return 2;
if (memo[n] != -1) return memo[n]; // 如果已计算过，直接返回结果
memo[n] = climbStairsMemo(n - 1) + climbStairsMemo(n - 2); // 递归计算并记忆结果
return memo[n];
}
int main() {
int n = 5;
// 初始化备忘录
for (int i = 0; i < 100; i++) {
memo[i] = -1;
}
printf("Ways to climb %d stairs: %d\n", n, climbStairsMemo(n)); // 输出: 8
return 0;
}
记忆化搜索分析：
- 时间复杂度：
O(n)，因为每个子问题只会被计算一次。 - 空间复杂度：
O(n)，除了递归栈的空间外，还需要额外的memo数组。
4. 其他动态规划与记忆化搜索问题
4.1. 最小路径和
给定一个 m x n 的网格，从左上角到右下角的最小路径和。只能向下或向右移动。
动态规划解法：
#include <stdio.h>
int minPathSum(int grid[][3], int m, int n) {
int dp[m][n];
dp[0][0] = grid[0][0];
for (int i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
for (int j = 1; j < n; j++) dp[0][j] = dp[0][j-1] + grid[0][j];
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = grid[i][j] + (dp[i-1][j] < dp[i][j-1] ? dp[i-1][j] : dp[i][j-1]);
}
}
return dp[m-1][n-1];
}
int main() {
int grid[3][3] = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
printf("Minimum path sum: %d\n", minPathSum(grid, 3, 3)); // 输出: 7
return 0;
}
动态规划分析：
- 时间复杂度：
O(m * n)，遍历整个网格。 - 空间复杂度：
O(m * n)，用于存储每个格子的最小路径和。
4.2. 背包问题
给定 n 个物品，每个物品有一个重量和价值，背包的最大容量为 W，求能装入背包中的最大价值。
动态规划解法：
#include <stdio.h>
int knapsack(int W, int wt[], int val[], int n) {
int dp[n+1][W+1];
for (int i = 0; i <= n; i++) {
for (int w = 0; w <= W; w++) {
if (i == 0 || w == 0) {
dp[i][w] = 0;
} else if (wt[i-1] <= w) {
dp[i][w] = (val[i-1] + dp[i-1][w-wt[i-1]] > dp[i-1][w]) ?
val[i-1] + dp[i-1][w-wt[i-1]] : dp[i-1][w];
} else {
dp[i][w] = dp[i-1][w];
}
}
}
return dp[n][W];
}
int main() {
int val[] = {60, 100, 120};
int wt[] = {10, 20, 30};
int W = 50;
int n = sizeof(val) / sizeof(val[0]);
printf("Maximum value: %d\n", knapsack(W, wt, val, n)); // 输出: 220
return 0;
}
动态规划分析：
- 时间复杂度：
O(n * W)，遍历所有物品和容量。 - 空间复杂度：
O(n * W)，需要存储所有状态。
5. 总结
- 动态规划（DP）：适用于求解最优化问题，通常通过 状态转移方程 将问题拆解为子问题，并利用表格（如数组、矩阵等）存储子问题的解。
- 记忆化搜索（Memoization）：通过递归加缓存来避免重复计算，适用于递归问题，尤其是在存在重叠子问题的场景。
在《剑指 Offer（第 2 版）》中，动态规划和记忆化搜索是解决很多问题的核心技巧，掌握它们能够有效提高解题效率，避免暴力求解导致的性能问题。
发表回复