✍️ 思想来源：灵茶山艾府
以经典题目「打家劫舍（House Robber）」为例
LeetCode 198: https://leetcode.cn/problems/house-robber/

---

一、从递归出发：暴力思维的萌芽

我们先来看问题本身：

有一排房子，每间房里有一定的钱，但相邻的两间不能同时偷。求能偷的最大金额。

很自然地想到递归：

• 对于第 i 间房子，我们有两个选择：

  • 不偷：那答案就是前 i-1 间的最大收益；

  • 偷：那答案就是前 i-2 间的最大收益 + 当前房间的钱。

于是递归公式如下：

        f(i)=max(f(i−1),f(i−2)+nums[i])

👉 翻译成代码：

int dfs(int i, vector<int>& nums) {
    if (i < 0) return 0; // 没房子可偷
    return max(dfs(i - 1, nums), dfs(i - 2, nums) + nums[i]);
}

缺点：大量重复计算。
例如，当求 f(4) 时，f(3) 和 f(2) 会反复被算多次。

---

二、递归 + 记忆化：让重复计算消失

灵神的思路：加缓存（记忆化）
——用一个数组保存已经算过的结果。

int dfs(int i, vector<int>& nums, vector<int>& memo) {
    if (i < 0) return 0;
    if (memo[i] != -1) return memo[i];  // 已计算过
    return memo[i] = max(dfs(i - 1, nums, memo), dfs(i - 2, nums, memo) + nums[i]);
}

int rob(vector<int>& nums) {
    vector<int> memo(nums.size(), -1);
    return dfs(nums.size() - 1, nums, memo);
}

✅ 时间复杂度：O(n)
✅ 空间复杂度：O(n)（递归栈 + 记忆数组）

---

三、从记忆化递归 → 递推：思维反转！

递归其实就是递+归，其实真正得到答案的过程是这个归，那我们完全可以只保留归。

dfs如何变成递推：dfs相当于是从上往下搜索，然后从下往上计算，递推就是自底向上计算，所以，我们当dfs改成数组，将递归改成循环。

我们可以直接从最小子问题开始，一步步往上推。

递推关系同样是：

        f[i]=max(f[i−1],f[i−2]+nums[i−1])

实现：

int rob(vector<int>& nums) {
    int n = nums.size();
    vector<int> f(n + 2);  // 多两个避免边界问题
    for (int i = 0; i < n; i++) {
        f[i + 2] = max(f[i + 1], f[i] + nums[i]);
    }
    return f[n + 1];
}

🧩 对应表格举例：

i	房子金额	f[i]	f[i+1]	f[i+2]
0	2	0	0	2
1	7	0	2	7
2	9	2	7	11
3	3	7	11	11
4	1	11	11	12

最终答案 f[n+1] = 12

---

四、空间优化：状态压缩的智慧

观察转移方程：

        f[i]=max(f[i−1],f[i−2]+nums[i])

可以发现：

• 每一步只用到前两个状态（f[i-1] 和 f[i-2]）。

所以我们完全可以只保存两个变量，而不用整个数组！

int rob(vector<int>& nums) {
    int f0 = 0, f1 = 0;
    for (int x : nums) {
        int new_f = max(f1, f0 + x);
        f0 = f1;
        f1 = new_f;
    }
    return f1;
}

✅ 时间复杂度：O(n)
✅ 空间复杂度：O(1)

这一步就是灵神常说的：“从状态定义中观察冗余信息，进一步压缩空间”。

附：复杂度的分析————状态个数*单个状态的时间