Saturday, July 25, 2026

🔬 Saturday Deep Dive: 动态规划一维 DP — 从爬楼梯到 LIS (15 min read)

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

🔥 Day 100 milestone!

Overview / 概述

中文：

动态规划（Dynamic Programming，DP）是面试中最难攻克、也最值得投入的算法专题。很多候选人看到 DP 题就慌——因为它没有固定套路，只有思维框架。本期深度解析一维 DP 的核心模式：从最简单的 Climbing Stairs，到经典的 Coin Change、House Robber，再到稍难的 Longest Increasing Subsequence（LIS）。掌握这条学习路径，你就打通了 DP 的任督二脉。

English：

Part 1: Theory / 理论基础 (5 min)

什么是 DP？/ What is DP?

中文：

DP 的本质是：把大问题拆成小问题，记住小问题的答案，避免重复计算。

两个必要条件：

1. 最优子结构（Optimal Substructure）：大问题的最优解可以由子问题的最优解构成
2. 重叠子问题（Overlapping Subproblems）：同一个子问题会被多次求解

两种实现方式：

• Top-down（记忆化递归）：从大问题出发，递归解小问题，用 memo 缓存结果
• Bottom-up（迭代填表）：从最小子问题出发，逐步构建答案

English：

DP's essence: break big problems into smaller ones, remember the answers, avoid recomputation.

Two prerequisites:

1. Optimal Substructure: the optimal answer to a big problem can be built from optimal answers to subproblems
2. Overlapping Subproblems: the same subproblem gets solved many times without DP

Two implementations:

• Top-down (memoization): start from the big problem, recurse, cache results in a memo dict
• Bottom-up (tabulation): start from base cases, fill a DP table iteratively

DP 的思维框架 / The DP Mental Model

Step 1: 定义状态 — dp[i] 代表什么？
         Define state — what does dp[i] mean?

Step 2: 推导转移方程 — dp[i] 如何从之前的状态得到？
         Find recurrence — how does dp[i] relate to dp[i-1], dp[i-2], ...?

Step 3: 确定初始值 — dp[0], dp[1] 等基础情况
         Establish base cases — what are dp[0], dp[1]?

Step 4: 确定计算顺序 — 通常从小到大
         Determine order — usually left to right

Step 5: 提取答案 — dp[n] 还是 max(dp)?
         Extract answer — dp[n] or max(dp[i])?

一维 DP 的四种核心模式 / Four Core 1D DP Patterns

Part 2: Step-by-Step Implementation / 一步一步实现 (8 min)

Problem 1: Climbing Stairs (Easy) — DP 入门

🔗 https://leetcode.com/problems/climbing-stairs/

📹 https://www.youtube.com/watch?v=Y0lT9Fck7qI

题意 / Problem: n 阶楼梯，每次走 1 或 2 步，有多少种走法？

def climbStairs(n: int) -> int:
    # Base cases
    # 0 stairs: 1 way (do nothing)
    # 1 stair:  1 way (one single step)
    if n <= 1:
        return 1
    
    # dp[i] = number of distinct ways to reach stair i
    # Recurrence: to reach stair i, you came from i-1 (one step)
    #             OR from i-2 (two steps) → add both
    # This is literally Fibonacci!
    
    # Space-optimized: only need last two values
    prev2, prev1 = 1, 1  # dp[0]=1, dp[1]=1
    
    for i in range(2, n + 1):
        curr = prev1 + prev2   # dp[i] = dp[i-1] + dp[i-2]
        prev2 = prev1
        prev1 = curr
    
    return prev1

# Test
assert climbStairs(2) == 2   # [1+1, 2]
assert climbStairs(3) == 3   # [1+1+1, 1+2, 2+1]
assert climbStairs(5) == 8

关键洞察 / Key Insight: Climbing Stairs = Fibonacci. The DP table looks like: [1, 1, 2, 3, 5, 8, 13...]. Once you see this, you can solve in O(n) time, O(1) space.

Problem 2: House Robber (Medium) — 选或不选模式

🔗 https://leetcode.com/problems/house-robber/

📹 https://www.youtube.com/watch?v=73r3KWiEvyk

题意 / Problem: 一排房子，不能偷相邻两间，求最大金额。

def rob(nums: list[int]) -> int:
    # dp[i] = max money robbing from houses 0..i
    # At house i, we either:
    #   SKIP it:  dp[i] = dp[i-1]             (same as best up to i-1)
    #   ROB  it:  dp[i] = dp[i-2] + nums[i]   (can't rob i-1, so go back to i-2)
    # dp[i] = max(skip, rob) = max(dp[i-1], dp[i-2] + nums[i])
    
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    
    # Space-optimized: dp[i-2]=prev2, dp[i-1]=prev1
    prev2 = nums[0]               # dp[0] = first house value
    prev1 = max(nums[0], nums[1]) # dp[1] = max of first two
    
    for i in range(2, len(nums)):
        curr = max(prev1, prev2 + nums[i])  # skip vs rob
        prev2 = prev1
        prev1 = curr
    
    return prev1

# Test
assert rob([1, 2, 3, 1]) == 4    # rob house 0 (1) + house 2 (3)
assert rob([2, 7, 9, 3, 1]) == 12  # rob house 0 (2) + house 2 (9) + house 4 (1)

变体陷阱 / Common Variant: House Robber II (circular array). Split into two sub-problems: rob nums[0..n-2] OR nums[1..n-1], take the max.

Problem 3: Coin Change (Medium) — 无界背包模式

🔗 https://leetcode.com/problems/coin-change/

📹 https://www.youtube.com/watch?v=H9bfqozjoqs

题意 / Problem: 给定面值 coins，凑出 amount 的最少硬币数（每种硬币可用无限次）。

def coinChange(coins: list[int], amount: int) -> int:
    # dp[i] = minimum coins needed to make amount i
    # Initialize with infinity (impossible state)
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0  # base case: 0 coins needed to make amount 0
    
    # For each amount from 1 to target:
    # try every coin denomination
    # if we can make (i - coin), then dp[i] = dp[i-coin] + 1
    
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:  # can use this coin
                # Use this coin: costs 1 coin + whatever it took to make (i-coin)
                dp[i] = min(dp[i], dp[i - coin] + 1)
    
    # If still inf, amount is unreachable
    return dp[amount] if dp[amount] != float('inf') else -1

# Test
assert coinChange([1, 5, 10, 25], 41) == 4  # 25 + 10 + 5 + 1
assert coinChange([2], 3) == -1              # impossible
assert coinChange([1, 2, 5], 11) == 3        # 5 + 5 + 1

# Trace dp for coins=[1,5], amount=6:
# dp[0]=0
# dp[1]=min(inf, dp[0]+1)=1             (use coin=1)
# dp[2]=min(inf, dp[1]+1)=2             (use coin=1)
# dp[5]=min(dp[4]+1, dp[0]+1)=1         (use coin=5)
# dp[6]=min(dp[5]+1, dp[1]+1)=2         (5+1 or 1+1+1+1+1+1)

区分 0/1 背包 vs 无界背包 / 0-1 vs Unbounded:

• Coin Change = 无界背包（Unbounded Knapsack）: 每种硬币可用无限次，外层遍历 amount，内层遍历 coins
• 0/1 背包: 每件物品只能用一次，外层遍历物品，内层从大到小遍历容量（防止重复选取）

Problem 4: Longest Increasing Subsequence (Medium) — 序列 DP

🔗 https://leetcode.com/problems/longest-increasing-subsequence/

📹 https://www.youtube.com/watch?v=cjWnW0hdF1Y

题意 / Problem: 求数组的最长严格递增子序列长度。

def lengthOfLIS(nums: list[int]) -> int:
    n = len(nums)
    # dp[i] = length of longest increasing subsequence ENDING at index i
    # Key: "ending at i" — nums[i] must be the LAST element
    dp = [1] * n  # every element is a subsequence of length 1 by itself
    
    # For each position i, look back at all j < i
    # If nums[j] < nums[i], we can extend the subsequence ending at j
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:           # can extend
                dp[i] = max(dp[i], dp[j] + 1)  # extend LIS ending at j
    
    return max(dp)  # answer is the max across all ending positions

# Test
assert lengthOfLIS([10,9,2,5,3,7,101,18]) == 4  # [2,3,7,101] or [2,5,7,101]
assert lengthOfLIS([0,1,0,3,2,3]) == 4           # [0,1,2,3]
assert lengthOfLIS([7,7,7,7]) == 1               # all equal, not strictly increasing

# Trace [10,9,2,5,3,7]:
# dp = [1, 1, 1, ?, ?, ?]
# i=3 (nums[3]=5): j=2(nums[2]=2<5) → dp[3]=max(1,dp[2]+1)=2
# i=4 (nums[4]=3): j=2(nums[2]=2<3) → dp[4]=max(1,dp[2]+1)=2
# i=5 (nums[5]=7): j=2,3,4 all < 7 → dp[5]=max(dp[2]+1,dp[3]+1,dp[4]+1)=3
# dp = [1,1,1,2,2,3] → max=3

O(n log n) 优化 / Optimization — Patience Sorting:

import bisect

def lengthOfLIS_fast(nums: list[int]) -> int:
    # tails[i] = smallest tail of all increasing subsequences of length i+1
    # This is NOT the actual LIS, but its length equals LIS length
    tails = []
    
    for num in nums:
        pos = bisect.bisect_left(tails, num)  # find insertion point
        if pos == len(tails):
            tails.append(num)    # extend: new longest subsequence
        else:
            tails[pos] = num     # replace: maintain smallest possible tail
    
    return len(tails)

# This runs in O(n log n) — critical for n > 10^4
assert lengthOfLIS_fast([10,9,2,5,3,7,101,18]) == 4

Part 3: Edge Cases & Gotchas / 边界情况 (2 min)

中文：

1. 初始化陷阱

# Coin Change: 初始化为 float('inf')，不是 0
# 如果初始化为 0，min() 会永远返回 0 而不是正确答案

# House Robber: 处理 len(nums) == 1 的情况
# 如果只有一间房，直接返回 nums[0]

2. 空间优化时的更新顺序

# House Robber 空间优化：必须先保存 curr，再更新 prev
# 错误写法：
prev2 = prev1          # ❌ 此时 prev1 已被覆盖
prev1 = max(...)

# 正确写法：
curr = max(prev1, prev2 + nums[i])
prev2 = prev1          # ✓ 先移动 prev2
prev1 = curr           # ✓ 再更新 prev1

3. LIS 的"严格递增"

# 严格递增：nums[j] < nums[i]  (不含等号)
# 非严格递增：nums[j] <= nums[i]
# 题目通常要求严格，注意看清楚

4. Coin Change 无解时

# dp[amount] 仍为 inf → 返回 -1，不要忘记这个判断
return dp[amount] if dp[amount] != float('inf') else -1

English:

1. Initialization matters: Coin Change uses inf (not 0) as "impossible" sentinel. Using 0 will corrupt your min().
2. Update order in space optimization: Save curr before reassigning prev1/prev2.
3. Strict vs non-strict LIS: < vs <= changes the answer for arrays with duplicates.
4. Unreachable state: Always check if dp[target] is still inf before returning.

Part 4: Real-World Application / 实际应用 (2 min)

中文：

DP 不只是算法题里的玩具，它在工业界无处不在：

Senior Engineer 视角： 在分布式系统中，Coin Change 的思维直接对应资源调度问题：如何用最少数量的机器实例处理 N 个任务（容量有限的无界背包）。DP 的"记住子问题结果"哲学也是 memoization cache 的设计原理。

English:

DP isn't academic—it powers real systems:

• Git diff: The diff algorithm uses Edit Distance (DP) to compute minimal edits between two files
• Autocorrect: Spell checkers use Edit Distance to find nearest valid words
• Genomics: BLAST (DNA sequence alignment) uses Smith-Waterman, a DP variant
• Compilers: Optimal expression parsing uses interval DP (matrix chain multiplication)
• Networking: Bellman-Ford shortest path is literally DP over graph states
• Kubernetes scheduling: Bin-packing pod assignments → Knapsack DP approximations

The Coin Change mental model maps directly to resource allocation: "What's the minimum number of servers needed to handle N requests given server capacities?"

Part 5: Interview Simulation / 面试模拟 (3 min)

Setting: You're at the whiteboard. Interviewer says: "Solve Coin Change."

Q1: 你能先说说暴力解法吗？/ Can you start with the brute force?

A: 暴力法是递归穷举所有组合。对于金额 amount，尝试每种硬币 c，递归求解 amount - c，时间复杂度 O(S^n)（S=amount，n=硬币种数）。

Brute force: recursive enumeration of all combinations. For amount S with n coin types, time is O(S^n). This is exponential—unacceptable for large inputs.

Q2: 为什么这里用 Bottom-up DP 而不是 Top-down？/ Why bottom-up over top-down here?

A: 两种方法都可以，时间复杂度相同 O(S×n)。Bottom-up 的优势是没有递归栈溢出风险，对大 amount 更稳定。Top-down 写起来更直觉，适合思路整理阶段。

Both work with same O(S×n) complexity. Bottom-up avoids recursion stack overflow for large amounts. Top-down is more intuitive for working out the recurrence mentally—I often derive it top-down, then implement bottom-up.

Q3: 如果硬币不能重复使用（0/1 背包），怎么改？/ What if each coin can only be used once?

A: 需要把内层循环改成从大到小遍历（保证每枚硬币只计入一次）：

for coin in coins:
    for i in range(amount, coin - 1, -1):  # 从大到小！
        dp[i] = min(dp[i], dp[i - coin] + 1)

Reverse the inner loop to iterate amount down to coin. This prevents using the same coin twice because we process larger amounts before smaller ones.

Q4: LIS 的 O(n log n) 解法能解释一下 Patience Sort 的直觉吗？/ Can you explain Patience Sorting intuitively?

A: 想象打牌：把数字按纸牌放入"牌堆"，规则是每张牌只能放在比它大的牌上面（严格），否则新开一堆。最终牌堆数 = LIS 长度。bisect_left 找到应该放置的最左边牌堆位置，用当前数字替换该堆顶部（保持最小尾部，为后续更多牌留空间）。

Think of it like the card game Patience (Solitaire): place each number on the leftmost pile whose top card is ≥ current number, or start a new pile. The number of piles equals the LIS length. Binary search finds the placement in O(log n) per card.

Q5: House Robber II（环形）怎么处理？/ How do you handle the circular variant?

A: 关键观察：在环形数组中，第一个和最后一个房子不能同时被抢。因此把问题拆成两个子问题：

1. 不考虑最后一个房子：rob(nums[0..n-2])
2. 不考虑第一个房子：rob(nums[1..n-1])

取两者最大值即可。时间 O(n)，空间 O(1)。

Key observation: first and last house are adjacent in a circle, so they can't both be robbed. Split into two linear sub-problems: rob nums[0..n-2] OR nums[1..n-1]. Take the max. Elegant reduction to the problem we already solved.

总结 / Summary

中文：

今天覆盖了 1D DP 的四种核心模式：

• 线性路径（Climbing Stairs）：Fibonacci 变体，先求小再求大
• 选或不选（House Robber）：每个位置二选一，转移方程 max(skip, take)
• 无界背包（Coin Change）：每个状态依赖更小的状态，可重复选择
• 序列 DP（LIS）：以每个元素"结尾"定义状态，最后取 max

English:

Four 1D DP patterns mastered today:

• Linear path (Climbing Stairs): Fibonacci-like, small → large
• Pick or skip (House Robber): binary choice at each step, max(skip, take)
• Unbounded knapsack (Coin Change): reusable items, build up from 0
• Sequence DP (LIS): define state as "ending at index i", take global max

🔗 NeetCode DP Playlist: https://www.youtube.com/playlist?list=PLot-Xpze53ldAVx3a_QCGQaGHvzFkVfxP

🔗 LeetCode DP Study Plan: https://leetcode.com/study-plan/dynamic-programming/