从Pell数列到动态规划入门：用OpenJudge这道题讲透递推与记忆化的本质-深圳市維司達科技有限公司

从Pell数列到动态规划入门：用OpenJudge这道题讲透递推与记忆化的本质

第一次接触动态规划（DP）时，很多人会被那些抽象的概念搞得晕头转向——状态转移方程、最优子结构、重叠子问题...这些术语听起来高大上，但真正动手写代码时却不知从何下手。其实，动态规划的核心思想远没有想象中那么复杂。今天我们就以OpenJudge和信息学奥赛中常见的Pell数列问题为例，用最接地气的方式带你理解DP的本质。

Pell数列是一个经典的递推序列，定义如下：第一项为1，第二项为2，从第三项开始每一项都是前一项的两倍加上前前一项（即aₙ = 2aₙ₋₁ + aₙ₋₂）。这个看似简单的数列背后，隐藏着动态规划的两个核心实现范式：自底向上的递推和自顶向下的记忆化递归。通过这个具体案例，你将直观理解DP如何将复杂问题分解为简单子问题，并通过存储中间结果避免重复计算。

1. Pell数列问题与动态规划的天然联系

Pell数列本身就是一个天然的动态规划问题。让我们先看看为什么这么说。

动态规划适用的三个条件：

问题可以分解为相互重叠的子问题
子问题具有最优子结构（局部最优解能推导出全局最优解）
需要避免子问题的重复计算

Pell数列完美符合这三个条件。计算第n项需要知道第n-1和第n-2项，这体现了子问题的重叠性；每一项的值只依赖于前两项，这是最优子结构的体现；如果直接使用递归而不存储中间结果，计算aₙ时会重复计算aₙ₋₁和aₙ₋₂多次，导致指数级的时间复杂度。

1.1 状态定义：从数列到DP表

在动态规划中，第一步也是最重要的一步就是定义"状态"。对于Pell数列，状态定义非常直观：

dp[i]：表示Pell数列的第i项的值

初始状态也很明确：

dp[1] = 1 dp[2] = 2

这种状态定义方式几乎是从问题描述直接转化而来，这也是为什么Pell数列特别适合作为DP入门案例的原因之一。

1.2 状态转移方程：递推关系的数学表达

有了状态定义后，我们需要建立状态之间的关系，也就是状态转移方程。对于Pell数列，根据定义可以直接写出：

dp[i] = (2 * dp[i-1] + dp[i-2]) % 32767

这里的取模操作是题目要求的，防止数值过大。这个简单的方程已经包含了动态规划的核心——当前状态只依赖于有限的几个前驱状态。

2. 自底向上的递推解法

自底向上（Bottom-up）是动态规划最直接的实现方式，也是初学者最容易理解的方法。它的核心思想是从最小的子问题开始，逐步构建更大的问题的解。

2.1 递推解法的实现步骤

让我们用代码来展示这个过程：

def pell_sequence(n): if n == 1: return 1 if n == 2: return 2 dp = [0] * (n + 1) dp[1], dp[2] = 1, 2 for i in range(3, n + 1): dp[i] = (2 * dp[i-1] + dp[i-2]) % 32767 return dp[n]

这个实现有几个关键点：

处理基本情况（n=1和n=2）
初始化DP数组
按顺序填充DP数组

时间复杂度分析：

预处理阶段：O(n)
查询阶段：O(1)（如果预处理足够大的n）

2.2 空间优化：滚动数组技术

观察状态转移方程，我们发现当前状态只依赖于前两个状态。这意味着我们不需要存储整个DP数组，只需要保存最近的两个值即可：

def pell_sequence_optimized(n): if n == 1: return 1 if n == 2: return 2 a, b = 1, 2 # 分别代表dp[i-2]和dp[i-1] for _ in range(3, n + 1): a, b = b, (2 * b + a) % 32767 return b

这种优化将空间复杂度从O(n)降到了O(1)，是动态规划中常用的空间优化技巧。

3. 自顶向下的记忆化递归解法

与自底向上相对的是自顶向下（Top-down）方法，也就是记忆化递归。这种方法更符合人类的自然思维模式：要解决大问题，先解决其子问题。

3.1 普通递归的问题

先看看没有记忆化的递归实现：

def pell_recursive(n): if n == 1: return 1 if n == 2: return 2 return (2 * pell_recursive(n-1) + pell_recursive(n-2)) % 32767

这个实现虽然简洁，但效率极低。计算pell_recursive(5)的调用树如下：

pell(5) ├── pell(4) │ ├── pell(3) │ │ ├── pell(2) │ │ └── pell(1) │ └── pell(2) └── pell(3) ├── pell(2) └── pell(1)

可以看到pell(3)被计算了两次，pell(2)被计算了三次。随着n增大，重复计算会呈指数级增长。

3.2 记忆化：避免重复计算的魔法

记忆化技术就是在递归的基础上加上缓存，存储已经计算过的结果：

def pell_memoization(n, memo=None): if memo is None: memo = {1: 1, 2: 2} if n not in memo: memo[n] = (2 * pell_memoization(n-1, memo) + pell_memoization(n-2, memo)) % 32767 return memo[n]

现在计算pell_memoization(5)时：

第一次遇到pell(3)时会计算并存储结果
第二次遇到pell(3)时直接返回缓存结果

时间复杂度分析：

每个子问题只计算一次：O(n)
查询缓存：O(1)

记忆化递归将时间复杂度从指数级降到了线性级，是动态规划中极其重要的技术。

4. 两种范式的对比与应用场景

理解了两种实现方式后，我们来系统比较它们的优缺点：

特性	自底向上递推	自顶向下记忆化递归
思维模式	迭代式，从小问题到大问题	递归式，从大问题分解到小问题
实现难度	相对简单	需要处理递归和记忆化
空间复杂度	通常可以优化到O(1)	需要O(n)的缓存空间
计算顺序	必须按顺序计算所有子问题	只计算需要的子问题
适用场景	子问题依赖关系简单明确	子问题依赖关系复杂或不确定

在实际应用中：

当问题结构清晰、子问题依赖简单时（如Pell数列），推荐使用自底向上方法
当问题复杂、子问题依赖关系不明确或不需要计算所有子问题时，记忆化递归更有优势

5. 从Pell数列到更一般的动态规划问题

理解了Pell数列的解法后，我们可以将其中的思想推广到更一般的动态规划问题。以下是动态规划解题的通用框架：

定义状态：明确dp[i]或dp[i][j]等表示什么
确定初始状态：找到最小子问题的解
建立状态转移方程：找出状态之间的关系
确定计算顺序：自底向上还是自顶向下
考虑优化：空间优化（如滚动数组）、剪枝等

以斐波那契数列为例，它与Pell数列非常相似：

状态定义：dp[i]表示第i项斐波那契数
初始状态：dp[0]=0, dp[1]=1
状态转移：dp[i] = dp[i-1] + dp[i-2]

再比如爬楼梯问题（每次可以爬1或2个台阶，问n个台阶有多少种爬法）：

状态定义：dp[i]表示i个台阶的爬法数
初始状态：dp[0]=1, dp[1]=1
状态转移：dp[i] = dp[i-1] + dp[i-2]

这些问题的共同点是当前状态只依赖于有限个前驱状态，这种特性使得它们适合用动态规划高效解决。

6. 动态规划的常见误区与调试技巧

初学者在实现动态规划时经常会遇到一些典型问题：

常见误区：

状态定义不明确或不合适
遗漏初始条件
状态转移方程错误
计算顺序不正确
没有处理边界条件

调试技巧：

打印DP表：对于小规模输入，打印整个DP数组检查值是否正确

def pell_debug(n): dp = [0] * (n + 1) dp[1], dp[2] = 1, 2 for i in range(3, n + 1): dp[i] = (2 * dp[i-1] + dp[i-2]) % 32767 print(f"dp[{i}] = {dp[i]}") return dp[n]