🔄 复习日 / Review Day — Day 135

Date: 2026-09-22

Phase: Expert | Topics: 1D Dynamic Programming Block (Days 131–134)

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

🔥 1-day streak!

回顾内容 / Topics Covered (Days 131–134)

📝 Quick Quiz — 3 Mini-Reviews

Q1: [💻 Algorithms — House Robber II]

House Robber I 是线性数组，House Robber II 是循环数组（第一个和最后一个房子相邻）。你会如何修改 DP 来处理这个约束？

House Robber I is a linear array. House Robber II adds a circular constraint: the first and last houses are adjacent and can't both be robbed. How do you modify the DP to handle this?

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

核心思路 / Key Insight: 把一个循环问题拆成两个线性子问题。

将数组分成两段分别跑标准 House Robber DP，取最大值：

• 子问题 1：houses[0..n-2]（排除最后一个）
• 子问题 2：houses[1..n-1]（排除第一个）

答案是两个子问题结果的最大值。

Split into two linear subproblems:

• Run standard O(n) House Robber on houses[0..n-2] (exclude last)
• Run standard O(n) House Robber on houses[1..n-1] (exclude first)
• Return max(result1, result2)

This works because in a valid circular solution, either the first house is robbed (so last isn't) or the last is robbed (so first isn't). The two subproblems cover both cases exhaustively.

def rob(nums):
    if len(nums) == 1: return nums[0]
    def rob_linear(arr):
        prev2, prev1 = 0, 0
        for n in arr:
            prev2, prev1 = prev1, max(prev1, prev2 + n)
        return prev1
    return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))

时间 O(n)，空间 O(1)。

</details>

Q2: [💻 Algorithms — Decode Ways]

在 Decode Ways 中，DP 转移方程有两个部分。什么时候应该加 dp[i-2]（双位数解码）？什么情况下 dp[i-1] 反而为 0 不能加？

In Decode Ways, the DP recurrence has two parts. When should you add dp[i-2] (two-digit decode)? When is dp[i-1] actually 0 and cannot be added?

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

核心思路 / Key Insight: 单位数和双位数的有效性检查各自独立。

单位数解码 (dp[i] += dp[i-1]): 当 s[i-1] != '0' 时成立（'0' 不是合法字母映射）

双位数解码 (dp[i] += dp[i-2]): 当 s[i-2:i] 在 "10" 到 "26" 之间时成立

陷阱：s[i-1] == '0' 的情况

• 如果当前字符是 '0'，单位数解码无效（dp[i-1] 不能加）
• 但如果 s[i-2] 是 '1' 或 '2'，双位数解码有效（"10" 或 "20"）
• "00" → 完全无效，dp[i] = 0（注意防止死胡同）

Single-digit: Add dp[i-1] when s[i-1] != '0'

Two-digit: Add dp[i-2] when 10 <= int(s[i-2:i]) <= 26

def numDecodings(s):
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1 if s[0] != '0' else 0
    for i in range(2, n + 1):
        one = int(s[i-1])
        two = int(s[i-2:i])
        if one >= 1:
            dp[i] += dp[i-1]    # single-digit valid
        if 10 <= two <= 26:
            dp[i] += dp[i-2]    # two-digit valid
    return dp[n]

The key edge case: "06" → two-digit 06 = 6 < 10, invalid. Only 10–26 count.

</details>

Q3: [💻 Algorithms — Palindromic Substrings vs Longest Palindromic Substring]

这两道题用的是同一种"中心扩展"技巧，但输出不同。请解释：(1) 如何同时处理奇数长度和偶数长度回文？(2) 这两道题分别返回什么？

Both problems use the same "expand around center" technique but return different things. Explain: (1) How do you handle both odd and even length palindromes? (2) What does each problem return?

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

核心思路 / Key Insight: 每个字符（奇数）和每对相邻字符（偶数）各是一个潜在的回文中心。

中心扩展 / Expand Around Center:

• 奇数长度：以 (i, i) 为中心扩展 → 处理 "aba" 类型
• 偶数长度：以 (i, i+1) 为中心扩展 → 处理 "abba" 类型
• 共 2n - 1 个中心，每个最多扩展 O(n)，总体 O(n²) 时间，O(1) 空间

Palindromic Substrings (#647) — 返回计数 / returns count:

def countSubstrings(s):
    count = 0
    def expand(l, r):
        nonlocal count
        while l >= 0 and r < len(s) and s[l] == s[r]:
            count += 1
            l -= 1; r += 1
    for i in range(len(s)):
        expand(i, i)    # odd
        expand(i, i+1)  # even
    return count

Longest Palindromic Substring (#5) — 返回子串 / returns substring:

def longestPalindrome(s):
    res, resLen = "", 0
    def expand(l, r):
        nonlocal res, resLen
        while l >= 0 and r < len(s) and s[l] == s[r]:
            if r - l + 1 > resLen:
                res, resLen = s[l:r+1], r - l + 1
            l -= 1; r += 1
    for i in range(len(s)):
        expand(i, i); expand(i, i+1)
    return res

区别 / Difference:

• #647: accumulate count per expansion
• #5: track max length + start index
• Both: O(n²) time, O(1) space — better than DP's O(n²) space

</details>

💡 复习巩固记忆，螺旋式上升。这4天的 DP 模式：线性 DP + 边界条件处理，是面试高频考点。

💡 Spaced repetition builds lasting memory. This week's theme: 1D DP with tricky boundary conditions — house constraints, circular arrays, character validity checks.

📅 明天继续新内容！Tomorrow back to new content!