递归慢是因为重复计算重叠子问题，如斐波那契中fib(5)被多次重复计算；动态规划通过缓存中间结果（记忆化）或自底向上递推来避免重复计算。
为什么递归慢？先看一个典型例子
很多初学者写 fibonacci 时直接用递归：int fib(int n) { return n 。表面简洁，但 <code>fib(40) 就要算几千万次——因为重复子问题没缓存，fib(5) 可能被算上百遍。
动态规划不是“换种写法”，而是强制你把中间结果记下来，避免重算。核心动作就两个：识别重叠子问题、加一层缓存或改递推顺序。
记忆化递归（Memoization）怎么加？三步到位
这是最贴近原递归的优化方式，改动最小、逻辑最清晰：
- 在函数外或作为参数传入一个
std::unordered_map<int int></int>或std::vector<int></int>（若输入范围确定） - 每次进入函数先查缓存：
if (memo[n] != -1) return memo[n]; - 递归计算完立刻存：
memo[n] = result;
注意点：
-
std::vector初始化要够大（比如memo.resize(n+1, -1)），否则越界访问 -
unordered_map更灵活，但哈希开销略高；对稀疏输入（如只调用fib(1),fib(100),fib(1000)）更合适 - 不要忘了初始化缓存值为无效态（如
-1或std::nullopt），否则fib(0)=0会被误判为未计算
改成自底向上递推（Tabulation）要注意什么？
这一步本质是把递归调用栈“拍平”成数组迭代：
- 明确状态定义：比如
dp[i]表示fib(i) - 写出状态转移方程：
dp[i] = dp[i-1] + dp[i-2] - 确定边界：
dp[0] = 0; dp[1] = 1; - 循环顺序必须从小到大，确保依赖项已计算
常见坑：
- 数组大小写错：需要
dp.size() == n+1，不是n - 边界处理漏掉
n==0或n==1的特判，导致访问dp[-1] - 空间可优化：本例中只需保留前两项，
int a=0, b=1, c;迭代即可，不必开整个vector
什么时候该用 DP？别硬套
DP 不是万能解药。判断标准很实在：
- 问题能拆成子问题，且子问题高度重叠（递归树里大量相同节点）
- 子问题答案不依赖后续决策（无后效性），比如路径题中“只能向右/下走”就满足，而带状态约束（如“最多选 3 个奇数”）需额外维度
- 输入规模在内存和时间可承受范围内（
O(n²)状态对n=10⁴就可能爆内存）
真正卡住人的，往往不是写不出状态转移式，而是没想清楚“状态”到底该记录什么——比如背包问题里，是记“前 i 个物品在容量 j 下的最大价值”，而不是“用了哪些物品”。状态设计错了，后面全白搭。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
