记忆化搜索

一句话理解

记忆化搜索：递归 + 存结果。

为什么要学

写着像 DFS，本质是 DP。

讲解

算过 f(state) 就记下。顺序由递归自然保证。

例子

int dfs(int i) {
    if (i <= 1) return 1;
    if (memo[i]) return memo[i];
    return memo[i] = dfs(i-1) + dfs(i-2);
}

斐波那契记忆化。

常见错误

• memo 0 既当没算过又当答案 0。用 vis 或 -1。
• 状态不哈希。