动态规划：从斐波那契到背包的"记忆化"思维

算斐波那契数列，最直白的写法是递归：f(n)=f(n-1)+f(n-2)。但当你算 f(50)，会发现它慢得离谱——因为 f(50) 要算 f(49) 和 f(48)，而 f(49) 又要重算一遍 f(48)……同一个子问题被反复计算成千上万次。

解法朴素到惊人：把算过的答案存进一张表，下次直接查。这叫记忆化（memoization）。加上它，复杂度从指数级 O(2ⁿ) 骤降到线性 O(n)。而把"递归+备忘"翻成"自底向上填表"，就是动态规划（DP）的雏形。

DP 的通用套路只有两步：找最优子结构（大问题的最优解由小问题的最优解组成）+ 设计状态与转移。经典如0-1 背包（缺口 E2）：每件物品选或不选，用 dp[i][w] 表示"前 i 件、容量 w 下的最大价值"，状态转移一目了然；再如最长公共子序列 LCS（缺口 E3）、编辑距离（缺口 E4，生物信息序列比对的基础）。

DP 是必学必会算法轨道里尚未补齐的核心缺口（E 系列），却也是面试与竞赛的"分水岭"题型。它的难点不在代码，而在状态怎么定义——一旦定义对，填表只是体力活。入门节里我们强调"先证明对、再谈快"，在 DP 这里同样适用：先想清子结构，再动手写转移。

从斐波那契到背包，差的就是"别重复劳动"这五个字。把这句刻进脑子里，你就拿到了打开 DP 大门的钥匙。

关联推荐

• GPT-5.6 递归自我改进 — 递归是 DP 的起点，看它如何被 AI 重新演绎
• （本批「算法与问题求解入门」KU 发布后回填互链）