← 2026-09-08 📂 All Days 2026-09-10 →

📊 Day 130 Review — 2026-09-09

进度 / Progress:

NeetCode: 101/150 · SysDesign: 60/40 · Behavioral: 60/40 · Frontend: 37/50 · AI: 30/30

🔥 2-day streak!

🔄 复习日 / Review Day

今天是复习日！回顾过去4天的内容。

Today is review day! Let's revisit the past 4 days.

覆盖主题 / Topics covered:

Day 126: Climbing Stairs (爬楼梯 — 基础1D DP)
Day 127: 背包问题两大模式 — Coin Change & Partition Equal Subset Sum (Deep Dive)
Day 128: Min Cost Climbing Stairs (最低花费爬楼梯 — 1D DP变体)
Day 129: House Robber (打家劫舍 — 相邻约束DP)

📝 Quick Quiz — 3 Mini-Reviews

Q1: [💻 Algorithms — 1D DP 基础]

Climbing Stairs 和 Min Cost Climbing Stairs 都是1D DP的经典题。请问：这两题的状态转移方程有何不同？Min Cost 版本需要额外处理什么？

Climbing Stairs and Min Cost Climbing Stairs are both 1D DP classics. How do their recurrence relations differ? What extra consideration does the Min Cost version require?

<details><summary>显示答案 / Show Answer</summary>

Climbing Stairs: dp[i] = dp[i-1] + dp[i-2]

你只关心到达第 i 级台阶的方案数，每步可走1或2步，没有代价。

Min Cost Climbing Stairs: dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])

关键区别：需要在转移时加上"离开"该台阶的代价，而不只是方案数。另外需要特别处理终点——到达 n 级台阶时可以从 n-1 或 n-2 起跳，所以答案是 min(dp[n-1], dp[n-2])，不需要 cost[n]。

Key insight: Min Cost adds a cost layer to the standard climbing pattern. The "pay to leave" framing vs "pay to enter" is a common confusion point — in LeetCode #746, you pay cost[i] when you step on i, then you can jump from there.

</details>

Q2: [💻 Algorithms — House Robber 模式]

House Robber 的核心约束是"不能抢相邻两家"。这衍生出一个经典的 skip-or-take DP 模式。请写出状态转移方程，并说明为什么空间可以优化到 O(1)？

House Robber's constraint is "can't rob two adjacent houses." Write the recurrence relation and explain why O(1) space is achievable.

<details><summary>显示答案 / Show Answer</summary>

状态转移:

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

对于每个房子 i，你有两个选择：

不抢：延续前一步的最大值 dp[i-1]
抢：前两步的最大值加上当前房子 dp[i-2] + nums[i]

O(1) 空间优化原理： dp[i] 只依赖 dp[i-1] 和 dp[i-2] 两个值，所以只需要两个变量滚动更新：

prev2, prev1 = 0, 0
for n in nums:
    prev2, prev1 = prev1, max(prev1, prev2 + n)
return prev1

Pattern recognition: 任何时候你看到 "只依赖前两个状态" + "从第 i 个选or不选"，立刻想到这个滚动变量优化。House Robber II（环形）只是在线性版本上跑两遍（0..n-2 和 1..n-1）取最大。

</details>

Q3: [💻 Algorithms — 背包问题两大模式]

Deep Dive Day 127 覆盖了 Coin Change（无限背包）和 Partition Equal Subset Sum（0/1背包）。请比较这两种模式的核心区别：DP数组初始化方式、遍历顺序有何不同？为什么？

Day 127 deep dive covered Coin Change (unbounded knapsack) and Partition Equal Subset Sum (0/1 knapsack). Compare the two: how do DP array initialization and traversal order differ, and why?

<details><summary>显示答案 / Show Answer</summary>

特征	Coin Change（无限背包）	Partition Equal Subset Sum（0/1背包）
每个物品	可重复使用	只能用一次
1D DP遍历	正序（从小到大）	逆序（从大到小）
初始化	`dp[0]=0`, 其余 `inf`	`dp[0]=True`, 其余 `False`

为什么遍历方向不同？

正序（无限背包）： 当计算 dp[j] 时，dp[j - coin] 已经是"当前轮"更新后的值，意味着同一个硬币被重复"用"了——这正是我们想要的。
逆序（0/1背包）： 从右往左更新确保每个物品只被使用一次。dp[j] 更新时，dp[j - num] 仍是"上一轮"的值（代表没用当前这个 num）。

**口诀：** 无限 → 正序，唯一 → 逆序。记住这一条，两大背包模式手到擒来。

</details>

💡 复习巩固记忆，螺旋式上升。Review reinforces memory; spiral learning compounds.

📅 明天继续新内容！Tomorrow: new content resumes!

Wednesday, September 9, 2026

📊 Day 130 Review — 2026-09-09

📝 Quick Quiz — 3 Mini-Reviews