从Pell数列到动态规划入门：用C++讲透递推与记忆化搜索的核心思想

第一次接触动态规划时，很多人会被那些抽象的概念吓退——状态转移方程、最优子结构、重叠子问题...这些术语听起来就像一堵高墙。但当我真正理解动态规划后，才发现它其实就像搭积木一样直观。今天，我们就从一个简单的Pell数列入手，用C++代码拆解动态规划的核心思想，让你在30分钟内掌握这个看似高深的算法范式。

1. 为什么Pell数列是理解动态规划的完美起点

Pell数列的定义简单到令人惊讶：第1项是1，第2项是2，从第3项开始，每一项都是前一项的两倍加上前前一项。用公式表示就是：

P(n) = 2*P(n-1) + P(n-2) (n ≥ 3)
P(1) = 1, P(2) = 2

这个数列看似普通，却包含了动态规划的所有关键要素：

• 递推关系 ：当前项由前两项决定
• 初始条件 ：明确的起点值
• 重复计算 ：直接递归会有大量冗余计算
• 优化空间 ：可以通过存储中间结果提升效率

在信息学奥赛（NOI）和OpenJudge等编程竞赛中，Pell数列常被用作动态规划的入门题目。它比斐波那契数列稍复杂，但又不像背包问题那样涉及多维状态，是理解DP思想的"黄金分割点"。

2. 暴力递归的陷阱与启示

让我们先看一个最直观的递归解法：

int pell(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    return (2 * pell(n-1) + pell(n-2)) % 32767;
}

这段代码简洁明了，但存在致命缺陷—— 指数级的时间复杂度 。计算P(5)时，调用树如下：

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

可以看到P(3)被计算了两次，随着n增大，重复计算会呈爆炸式增长。这就是动态规划要解决的核心问题之一—— 重叠子问题 。

提示：在算法竞赛中，当n达到10^6时，这种暴力递归会立即超时，必须寻找更高效的解法。

3. 自底向上的递推：动态规划的经典范式

动态规划的第一种实现方式是 递推法 ，也称为自底向上(bottom-up)方法。其核心思想是：

1. 定义状态：这里状态就是Pell数列的第i项
2. 确定初始条件：P[1]=1, P[2]=2
3. 建立状态转移方程：P[i] = (2*P[i-1] + P[i-2]) % 32767
4. 按顺序计算所有状态

C++实现如下：

#include <iostream>
using namespace std;

const int MAX_N = 1e6;
const int MOD = 32767;
int p[MAX_N + 1]; // p[i]表示Pell数列第i项

void precompute() {
    p[1] = 1;
    p[2] = 2;
    for (int i = 3; i <= MAX_N; ++i) {
        p[i] = (2 * p[i-1] + p[i-2]) % MOD;
    }
}

int main() {
    precompute();
    int n, k;
    cin >> n;
    while (n--) {
        cin >> k;
        cout << p[k] << endl;
    }
    return 0;
}

这种方法的时间复杂度是O(n)，预处理后每次查询只需O(1)时间。它的优势在于：

• 避免了递归开销
• 计算顺序明确，易于理解
• 适合处理大规模数据

但缺点是需要预先计算并存储所有可能用到的状态，当状态空间很大时会消耗较多内存。

4. 记忆化搜索：优雅的自顶向下解法

如果你更喜欢递归的思维模式， 记忆化搜索 （Memoization）提供了另一种选择。它保留了递归的直观性，同时通过缓存结果避免了重复计算。

记忆化搜索的实现步骤：

1. 定义递归函数和状态
2. 添加缓存机制存储已计算的结果
3. 在递归前检查缓存
4. 计算结果后存入缓存

C++实现：

#include <iostream>
#include <cstring>
using namespace std;

const int MAX_N = 1e6;
const int MOD = 32767;
int memo[MAX_N + 1]; // 记忆化数组

int pell(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    if (memo[n] != -1) return memo[n]; // 已计算过，直接返回
    
    return memo[n] = (2 * pell(n-1) + pell(n-2)) % MOD;
}

int main() {
    memset(memo, -1, sizeof(memo)); // 初始化为-1表示未计算
    int n, k;
    cin >> n;
    while (n--) {
        cin >> k;
        cout << pell(k) << endl;
    }
    return 0;
}

记忆化搜索的特点：

特性	描述
时间复杂度	O(n)，每个子问题只计算一次
空间复杂度	O(n)，需要存储所有可能的状态
优势	代码更接近问题定义，逻辑直观
劣势	递归调用有额外开销，可能栈溢出

注意：在实际编程竞赛中，对于极深的递归（如n>1e5），递推法通常更安全可靠。

5. 空间优化：滚动数组技巧

观察状态转移方程P[i] = 2*P[i-1] + P[i-2]可以发现，当前状态只依赖于前两个状态。这意味着我们不需要存储整个数组，只需保留最近的两个值即可。这种技巧称为 滚动数组 。

优化后的递推实现：

#include <iostream>
using namespace std;

const int MOD = 32767;

int pell(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    
    int a = 1, b = 2, c;
    for (int i = 3; i <= n; ++i) {
        c = (2 * b + a) % MOD;
        a = b;
        b = c;
    }
    return b;
}

int main() {
    int n, k;
    cin >> n;
    while (n--) {
        cin >> k;
        cout << pell(k) << endl;
    }
    return 0;
}

空间复杂度从O(n)降到了O(1)，这在处理极大n值时非常有用。滚动数组是动态规划中常用的优化手段，特别适用于状态转移只依赖有限前驱状态的情况。

6. 从Pell数列到通用动态规划框架

通过Pell数列这个简单例子，我们可以抽象出解决动态规划问题的一般步骤：

1. 定义状态 ：明确dp数组的含义（如dp[i]表示Pell数列第i项）
2. 确定初始条件 ：设置已知的最小子问题的解（如dp[1]=1, dp[2]=2）
3. 建立状态转移方程 ：找出状态间的关系（如dp[i] = 2*dp[i-1] + dp[i-2]）
4. 选择实现方式 ：递推或记忆化搜索
5. 考虑空间优化 ：如滚动数组等技巧

这个框架可以推广到更复杂的DP问题：

• 斐波那契数列：dp[i] = dp[i-1] + dp[i-2]
• 爬楼梯问题：dp[i] = dp[i-1] + dp[i-2]
• 背包问题：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])

7. 动态规划的思维训练建议

掌握动态规划需要刻意练习。以下是我总结的有效训练方法：

• 从简单问题入手 ：先熟练掌握斐波那契、Pell数列等基础问题
• 手动画状态转移表 ：对于二维DP如背包问题，画表格能帮助理解
• 对比不同解法 ：对同一问题尝试递归、记忆化和递推三种实现
• 分析时间/空间复杂度 ：理解每种优化背后的代价与收益
• 参加编程竞赛 ：NOI、OpenJudge等平台有大量DP练习题

推荐练习题目难度递进：

1. 斐波那契数列（最基础）
2. Pell数列（本文案例）
3. 爬楼梯问题（变种斐波那契）
4. 最大子数组和（Kadane算法）
5. 01背包问题（经典二维DP）
6. 最长公共子序列（字符串DP）

记住，动态规划不是一蹴而就的。我在初学阶段也曾被各种状态转移方程困扰，但通过反复练习Pell数列这类基础问题，逐渐建立了DP思维模型。当你遇到更复杂的问题时，不妨回想这个简单的起点——所有复杂的DP问题，本质上都是Pell数列思想的延伸与组合。