GESP 六级 第 07 讲：一维动态规划

本讲定位：编程题第 1 题的主战场。2026 年 6 月「条形蛋糕」、2026 年 3 月「选数」都是一维 DP，25 分。客观题里单选第 14 题固定考「打家劫舍」式的转移填空，单选第 15 题考 DP 概念，判断题再出 1～2 条，合计 10 分以上。

五级第 06 讲的记忆化、六级第 08 讲的「贪心 vs DP」是为这一讲铺的路。学生已经见过 DP 的影子，本讲要把它变成一套能落笔的固定流程。

对应官方大纲：六级知识块 4「简单动态规划」——一维动态规划。

前置知识：四级第 04 讲（递推、数字三角形）、五级第 06 讲（递归与记忆化）、五级第 08 讲（贪心与最优子结构）。

代码说明：本讲代码均已用 g++ 11.5（-std=c++11）编译运行验证；两道真题程序在官方样例上输出一致，并与暴力枚举对拍（条形蛋糕 $n\le12$ 枚举全部切法、选数 $n\le9$ 枚举全部下标组合，各数百组）。

1. DP 是什么：带决策的递推

四级第 04 讲讲过递推：$f_n$ 由 $f_{n-1}, f_{n-2}, \ldots$ 算出来。动态规划就是递推加上一句「在这一步做个选择，取最优」。

$$ \boxed{\textbf{DP} = \textbf{递推} + \textbf{每步取 max/min}} $$

1.1 用得上 DP 的两个前提

⚠️ 判断题原题（2026 年 6 月六级判断第 10 题，官方答案「对」）：「动态规划问题通常要求具有最优子结构，并且常常存在重叠子问题」——正确。这两个词要能各解释一句。

和贪心的区别（五级第 08 讲）：贪心也要最优子结构，但还额外要求「贪心选择性质」（当前最优一定能通向全局最优）。没有那条性质就只能 DP。

1.2 递推写法 vs 记忆化写法

同一个 DP，可以从小往大递推（循环），也可以从大往小递归 + 记忆化。

⚠️ 判断题原题（2026 年 3 月六级判断第 10 题，官方答案「对」）：「状态空间相同且没有重复计算的情况下，『状态转移方程 + 递推』与『递归 + 记忆化搜索』的时间复杂度通常相同」——正确。

因为两者算的是同一批状态、每个状态算一次。区别只在：递推更快（没有函数调用开销）、记忆化更好写（不用想循环顺序）。

五级第 06 讲说「记忆化是 DP 的入门形态」，现在可以补完这句话：记忆化和递推是 DP 的两张面孔。

⚠️ 单选陷阱（2025 年 12 月六级单选第 15 题）：「动态规划方法的时间复杂度通常为状态的个数」——这句话是错的（该题问「错误的是」）。

$$ \boxed{\text{DP 时间复杂度} = \text{状态数} \times \text{每个状态的转移代价}} $$

$O(1)$

$O(n)$

$O(n)$

$O(n^2)$

只数状态数是不够的。

2. 四步法 ★（本讲的核心流程）

$$ \boxed{① \text{状态含义} \to ② \text{转移方程} \to ③ \text{边界} \to ④ \text{答案在哪}} $$

这四步必须写在草稿纸上再动键盘。 尤其第 ①步：说不清 dp[i] 是什么，后面全是瞎蒙。

2.1 热身：上楼梯

每次走 1 级或 2 级，问走到第 $n$ 级有多少种走法。