记忆化搜索（Memoization）和动态规划（Dynamic Programming, DP）都是解决重叠子问题的高效算法技术，但它们有着不同的实现方式和特点。
1. 基本概念
记忆化搜索（自顶向下）
本质：带有缓存机制的递归
方向：从原问题出发，分解为子问题（Top-down）
特点：
递归实现
只计算必要的子问题
通过缓存避免重复计算
动态规划（自底向上）
本质：迭代式的填表法
方向：从基础子问题开始，逐步构建最终解（Bottom-up）
特点：
迭代实现
通常计算所有可能的子问题
通过表格系统性地存储中间结果
2. 核心区别
| 特性 | 记忆化搜索 | 动态规划 |
|---|---|---|
| 实现方式 | 递归 | 迭代 |
| 计算顺序 | 自顶向下（从目标问题开始分解） | 自底向上（从基础情况开始构建） |
| 子问题计算 | 按需计算（懒计算） | 全部计算 |
| 空间复杂度 | 通常较高（递归栈+记忆表） | 通常可优化 |
| 代码可读性 | 更直观（接近问题描述） | 需要明确状态转移顺序 |
| 适用场景 | 子问题不明确或稀疏 | 子问题明确且密集 |
3. 具体对比
计算过程示例（以斐波那契数列为例）
记忆化搜索：
python
memo = {0:0, 1:1}
def fib(n):
if n not in memo:
memo[n] = fib(n-1) + fib(n-2)
return memo[n]→ 计算路径：fib(5)→fib(4)→fib(3)→fib(2)→fib(1)/fib(0)
动态规划：
python
def fib(n):
dp = [0,1] + [0]*(n-1)
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]→ 计算顺序：dp[0], dp[1], dp[2], ..., dp[n]
性能特点
记忆化搜索可能：
存在递归开销（栈空间、函数调用成本）
对于某些问题可能跳过不必要的子问题计算
更容易实现（特别是复杂的状态转移）
动态规划通常：
运行效率更高（无递归开销）
更容易进行空间优化（如滚动数组）
需要更明确的状态转移顺序
4. 如何选择
优先使用记忆化搜索当：
问题状态空间复杂或不规则
只有部分子问题需要被计算
递归关系直观但迭代顺序不明显
原型开发阶段（更易编写和调试）
优先使用动态规划当：
需要最优的空间复杂度
子问题有明确的计算顺序
需要极致的运行时性能
问题状态空间规整且密集
5. 经典问题对比
打家劫舍问题实现
记忆化搜索实现：
int dfs(int i, int* nums, int* memo) {
if (i < 0) return 0;
if (memo[i] != -1) return memo[i];
int not_rob = dfs(i-1, nums, memo);
int rob = dfs(i-2, nums, memo) + nums[i];
return memo[i] = max(not_rob, rob);
}动态规划实现：
int rob(int* nums, int n) {
if (n == 0) return 0;
int dp[n+1];
dp[0] = 0;
dp[1] = nums[0];
for (int i = 2; i <= n; i++) {
dp[i] = max(dp[i-1], dp[i-2] + nums[i-1]);
}
return dp[n];
}6. 相互转换
两者本质上是等价的，可以相互转换：
记忆化搜索 → DP：将递归改为迭代，明确计算顺序
DP → 记忆化搜索：将递推关系改写为递归，添加缓存
在实际应用中，许多问题先用记忆化搜索设计解法，再转换为DP进行优化是常见的解题路径。