动态规划与贪心

动态规划入门

DP = 重叠子问题 + 最优子结构。暴力递归加记忆化 → 自底向上填表。

斐波那契（入门）：

def fib(n):
    if n <= 1:
        return n
    dp = [0, 1]
    for i in range(2, n + 1):
        dp.append(dp[-1] + dp[-2])
    return dp[n]

一维 DP 经典

• 爬楼梯：dp[i] = dp[i-1] + dp[i-2]。
• 打家劫舍：dp[i] = max(dp[i-2]+nums[i], dp[i-1])。
• 最长递增子序列 O(n log n)：维护 tails 数组 + 二分。

背包家族

0-1 背包：

def knapsack01(w, wt, val):
    n = len(wt)
    dp = [0] * (w + 1)
    for i in range(n):
        for j in range(w, wt[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - wt[i]] + val[i])
    return dp[w]

完全背包：内层 j 正序。多重背包 二进制拆分。

二维 DP

• 编辑距离、最长公共子序列。
• 路径数（网格 unique paths）。

状态压缩：dp[mask][i] 旅行商、状压 DP（面试 Advanced）。

贪心

活动选择（按结束时间排序，选不冲突最多）：经典贪心。

跳跃游戏 II：维护当前能到达最远，步数 +1 当 i 到达当前边界。

区间问题：按右端点排序，合并/覆盖。

def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[1])
    # 或按起点排序合并相邻

硬币找零：面额可整除时贪心；一般面额需 DP。

DP vs 贪心

| | DP | 贪心 | |---|-----|------| | 保证最优 | 是（正确转移） | 需证明 | | 复杂度 | 常 O(n²) 或更高 | 常 O(n log n) | | 信号 | 计数/最值/方案数 | 区间、排序后局部最优 |

面试表达

定义 dp[i] 含义一句话。

写转移，举小例子验证。

空间优化：滚动数组、只保留两行。

Week 3 回溯见 week03-backtracking-graph。建议刷：爬楼梯、打家劫舍、0-1 背包、LIS、跳跃游戏、合并区间。

实战巩固与面试表达

本篇属于 8 周冲刺 week03-dp-greedy 主题。复习时先闭卷回答 frontmatter 中三张 flashcard，再展开口述两个「为什么」：为什么这种方案能 work、边界失败时如何降级。与相邻章节对照：算法篇强调复杂度与模板，Go 篇强调工程默认写法，中间件篇强调线上故障案例。

动手与自检清单

用 25 分钟限时做 1 道相关练习题或画出一张架构/数据结构示意图；用 5 分钟写 STAR 片段说明你在项目里是否用过类似技术。记录 3 个面试追问及你的标准答法，存入 /zh/notebook/master-plan 笔记。若某点不熟，回到对应 /chapters 交互 Lab 重新走一遍流程，比死记卡片更有效。

易错点提醒

避免只背名词不会画图；避免只说优点不谈 trade-off（性能、一致性、运维成本至少提一项）；避免把学习 Demo 说成百万 QPS 生产。回答时使用「场景 → 方案 → 结果 → 反思」四段式，体现工程成熟度。