记忆化与递推制表
缓存子问题答案的两种方法
记忆化与递推制表 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。
为什么要缓存
朴素递归会一遍又一遍地重复相同的工作。动态规划会将每个答案存储一次，从而避免重复计算。
fib(40) # slow: recomputes endlessly重叠子问题
当一个问题可以拆分为重叠子问题时，就适合使用动态规划。同一个较小的情况会出现在递归的多个分支中。
fib(5) needs fib(3) twice自顶向下：记忆化
记忆化就是普通递归加上缓存。您可以按需计算，并在第一次遇到每个输入时记住结果。
memo = {}在 Python 中轻松实现记忆化
lru_cache装饰器只需一行代码，就能将缓慢的递归变成快速的动态规划，并自动缓存每次调用。
from functools import lru_cache
@lru_cache(None)
def f(n): ...自底向上：制表法
制表法从最小的情况开始，逐步填充表格直到得到答案，使用循环而不是递归。
dp = [0] * (n + 1)用制表法计算斐波那契数列
先设置基础值，然后让每个单元格读取已经计算好的值。不需要调用栈，只需一个简洁的循环。
dp[0], dp[1] = 0, 1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]答案相同，方式不同
记忆化和制表法解决的是同一个递推关系。它们的区别只在方向：按需自顶向下，或按顺序自底向上。
何时优先使用记忆化
当递推关系自然易写，且您可能不需要计算每个状态时，请选择记忆化。
何时优先使用制表法
当循环需要高效执行、需要避开递归深度限制错误，或者无论如何都要计算完整表格时，请选择制表法。
import sys; sys.setrecursionlimit(10**6)注意递归深度限制
深层的记忆化递归可能触及 Python 的递归深度限制，并在大规模输入上因运行时错误而崩溃。
两者共享同一项代价
无论采用哪种方式，加速都来自每个状态只求解一次。总时间等于状态数量乘以每个状态的工作量。
快速检查
哪种方法使用循环以自底向上的方式填充表格？
回顾：两条路径，同一种动态规划
现在您可以用两种方式缓存子问题。记忆化采用自顶向下的递归；制表法采用自底向上的循环。请选择更清晰的方式。✨
常见问题解答
「记忆化与递推制表」课时是免费的吗？
是的 — 「记忆化与递推制表」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。
「记忆化与递推制表」这节课中我会学到什么？
缓存子问题答案的两种方法 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Competitive Programming Academy 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。
「记忆化与递推制表」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Competitive Programming Academy 课中编写并运行代码吗？
能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。