← 知识手册目录算法方法 · GESP 5 / 6 / 7 / 8 级相关跳到完整速查 ↓

PYTHON KNOWLEDGE · 16

动态规划、贪心与分治

根据子问题关系选择 DP、贪心或分治，并能说明状态、转移、顺序和正确性。

GESP 5 级GESP 6 级GESP 7 级GESP 8 级

01 · FORMAL DEFINITION

正式定义

动态规划保存重叠子问题的结果，通常依赖最优子结构；贪心每步做局部选择，必须证明它能导向全局最优；分治把问题拆成相互独立的同类子问题，递归求解后合并。

02 · MUST KNOW

学完这一章，必须说清楚的规则

  1. 01

    DP 四要素是状态含义、初始值、转移方程和计算顺序，最后还要明确答案位于哪里。

  2. 02

    记忆化搜索是自顶向下按需计算，表格 DP 是自底向上按依赖顺序计算。

  3. 03

    滚动数组只能压缩已经不会再使用的维度，更新方向必须避免覆盖仍需读取的旧状态。

  4. 04

    贪心要有交换论证、领先法或结构性质证明，样例上成功不是证明。

  5. 05

    归并排序把序列分半、分别排序再线性合并，时间 O(n log n)、额外空间 O(n)。

  6. 06

    LIS、LCS、0-1 背包和区间 DP 的状态定义不同，不能只替换模板变量名。

03 · RUNNABLE EXAMPLE

可运行示例与因果解释

PYTHON
values = [3, 1, 4, 2]
dp = [1] * len(values)
for i in range(len(values)):
    for j in range(i):
        if values[j] < values[i]:
            dp[i] = max(dp[i], dp[j] + 1)
print(max(dp, default=0))

COMMON PITFALLS

常见误区

  • 状态定义不含必要信息
  • 转移顺序读取到本轮新值
  • 没有证明就使用贪心
  • 把连续子数组和子序列混为一谈

SCOPE & BOUNDARIES

适用边界

  • 同一问题可能有多种复杂度方案，课程会同时保留清晰基线与优化版。
  • DP 不是枚举所有状态就结束；状态数与每次转移成本共同决定复杂度。