动态规划（DP）引入

一、什么是动态规划？

动态规划(Dynamic Programming，简称 DP)是一种通过求解子问题来解决原问题的方法。

它的核心思想是：保存子问题的结果，利用已有结果推导新的结果，避免重复计算。 常用于求最优值、统计方案数和判断可行性。

二、例子：爬楼梯

一段楼梯共有 $n$ 级，每次可以走 $1$ 级或 $2$ 级，从第 $0$ 级走到第 $n$ 级，共有多少种走法？迈步顺序不同视为不同方案。

例如，走到第 $3$ 级有 $3$ 种走法：$1+1+1$、$1+2$、$2+1$。

1. 定义状态

用 $dp[i]$ 表示走到第 $i$ 级的方案数。

2. 推导转移

考虑最后一步：

• 走 $1$ 级：从第 $i-1$ 级到达，有 $dp[i-1]$ 种方案。
• 走 $2$ 级：从第 $i-2$ 级到达，有 $dp[i-2]$ 种方案。

两类方案互不重叠，且覆盖所有可能，因此：

这就是状态转移方程，描述了当前状态与已有状态之间的关系。

3. 初始化并计算

其中，$dp[0]=1$ 表示“不走任何一步”也是一种方案。

按 $i$ 从小到大计算，保证每次转移所需的状态已经求出：

最终答案为 $dp[n]$。每个状态只计算一次，时间复杂度为 $O(n)$。

如果直接递归计算，求 $dp[5]$ 和 $dp[4]$ 时都会求到 $dp[3]$，产生重复计算；DP 将这些结果保存下来，供后续直接使用。

三、DP 中的几个重要概念

• 重叠子问题：同一个子问题会被多次遇到，保存结果可以避免重复计算。
• 无后效性：状态已经包含影响后续求解的必要信息，无须再追溯完整过程。例如，本题后续允许的走法只取决于当前楼梯级数。
• 最优子结构：对于最优化问题，原问题的最优解可以由相应子问题的最优解构成。计数型 DP 则需要正确划分并合并方案。

四、如何设计 DP？

1. 定义状态：每个状态表示什么？
2. 推导转移：当前状态由哪些状态得到？
3. 确定边界：哪些状态可以直接确定？
4. 安排顺序：怎样保证依赖的状态已经算好？
5. 确定答案：题目要求的结果对应哪个状态，或哪些状态的组合？

接下来学习的线性 DP，通常围绕序列位置或处理进度组织状态，例如“考虑前 $i$ 个元素”或“以第 $i$ 个元素结尾”。爬楼梯就是一个简单的例子。

注意：线性 DP 不一定只有一维状态，时间复杂度也不一定是 $O(n)$。