递推问题学习笔记

📚 来源：竞赛向综合拔高2 - 章节2. 递推问题 📅 整理时间：2026年4月25日 📝 题目数量：20道

---

📖 目录

1. 什么是递推
2. 递推的核心思想
3. 题目分类与详解
   • 一、经典数列递推
   • 二、计数类递推
   • 三、二维递推/动态规划入门
   • 四、路径计数类递推
4. 递推解题模板
5. 常见错误与技巧
6. 练习建议

---

什么是递推

递推是指通过已知的初始条件和递推关系式，逐步推导出后续结果的算法思想。

核心公式

f(n) = g(f(n-1), f(n-2), ...)

与递归的区别

特点	递推	递归
方向	从下往上，自底向上	从上往下，自顶向下
效率	通常更高效	可能有重复计算
实现	循环实现	函数调用自身
空间	通常O(1)或O(n)	需要栈空间

---

递推的核心思想

四步法

1. 定义状态：明确 f(n) 代表什么
2. 找出关系：推导 f(n) 与之前状态的关系
3. 确定初值：设置边界条件
4. 按序计算：从初值开始逐步推导

---

题目分类与详解

---

一、经典数列递推

📌 1. 兔子繁殖 (P4847)

问题描述：经典的斐波那契兔子繁殖问题。

递推关系：

f(n) = f(n-1) + f(n-2)

理解：

• 第n个月的兔子 = 上个月已有的兔子 + 这个月新出生的兔子
• 新出生的兔子 = 两个月前已有的兔子（它们现在可以繁殖）

代码模板：

long long fib[50];
fib[1] = 1, fib[2] = 1;
for (int i = 3; i <= n; i++) {
    fib[i] = fib[i-1] + fib[i-2];
}
cout << fib[n];

难点：大数处理，注意数据范围。

---

📌 2. Pell数列 (P4843)

问题描述：Pell数列定义。

递推关系：

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

与斐波那契的对比： | 数列 | 递推公式 | 特点 | |------|----------|------| | 斐波那契 | f(n) = f(n-1) + f(n-2) | 系数都为1 | | Pell | P(n) = 2*P(n-1) + P(n-2) | 系数变为2 |

代码模板：

long long pell[100];
pell[1] = 1, pell[2] = 2;
for (int i = 3; i <= n; i++) {
    pell[i] = 2 * pell[i-1] + pell[i-2];
}

---

📌 3. 汉诺塔的移动次数 (P4846)

问题描述：计算汉诺塔问题的最少移动次数。

递推关系：

h(n) = 2 * h(n-1) + 1
h(1) = 1

推导过程：

1. 把上面n-1个盘子从A移到B：h(n-1)次
2. 把最大的盘子从A移到C：1次
3. 把n-1个盘子从B移到C：h(n-1)次
4. 总共：2*h(n-1) + 1

通项公式：

h(n) = 2^n - 1

---

📌 4. 输出杨辉三角的前N行 (P4849)

问题描述：输出杨辉三角。

递推关系：

C[i][j] = C[i-1][j-1] + C[i-1][j]
C[i][0] = C[i][i] = 1

特点：

• 每行首尾都是1
• 中间每个数等于上方两数之和
• 第n行有n个元素

代码模板：

int c[35][35];
for (int i = 1; i <= n; i++) {
    c[i][1] = 1;
    c[i][i] = 1;
    for (int j = 2; j < i; j++) {
        c[i][j] = c[i-1][j-1] + c[i-1][j];
    }
}

---

二、计数类递推

📌 5. 铺地砖 (P4848) & 铺地砖-简化版 (P4858)

问题描述：用1×1、1×2、1×3的地砖铺满1×n的方格，有多少种铺法？

递推关系：

f(n) = f(n-1) + f(n-2) + f(n-3)

理解：

• 最后一块放1×1：前面有f(n-1)种
• 最后一块放1×2：前面有f(n-2)种
• 最后一块放1×3：前面有f(n-3)种

简化版：只考虑1×1和1×2两种地砖

f(n) = f(n-1) + f(n-2)

即斐波那契数列！

---

📌 6. 骨牌铺方格 (P4853) & 骨牌铺方格-简化版 (P4857)

问题描述：用骨牌铺满方格的方案数。

递推关系：

f(n) = f(n-1) + 2*f(n-2)  // 完整版
f(n) = f(n-1) + f(n-2)    // 简化版

关键理解：

• 简化版：同斐波那契
• 完整版：最后一块竖着放 + 最后两块横着放（2种方式）

---

📌 7. 平面分割问题 (P4852)

问题描述：n条封闭曲线把平面分割成多少区域？

递推关系：

f(n) = f(n-1) + 2*(n-1)
f(1) = 2

推导：第n条曲线与前面n-1条曲线各交于2点，每穿过一条曲线就新增2个区域。

通项公式：

f(n) = n^2 - n + 2

---

📌 8. 猴子吃桃问题 (P4813)

问题描述：猴子每天吃掉一半多一个，最后剩一个，求最初有多少。

递推关系（逆向思维）：

f(n) = 2 * (f(n+1) + 1)

或者正向：

a[i+1] = a[i] / 2 - 1

---

三、二维递推/动态规划入门

📌 9. 数塔问题 (P4845) & 数塔的行走路径 (P4855)

问题描述：从塔顶走到塔底，求最大路径和。

递推关系（自底向上）：

dp[i][j] = max(dp[i+1][j], dp[i+1][j+1]) + a[i][j]

关键：从下往上推，每步选更大的子路径。

求路径：需要记录选择，回溯输出。

---

📌 10. 摘花生问题 (P4850) & 摘花生问题2 (P4854)

问题描述：从左上角走到右下角，只能向右或向下，求最大花生数。

递推关系：

dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + a[i][j]

边界处理：

dp[1][1] = a[1][1]
dp[1][j] = dp[1][j-1] + a[1][j]  // 第一行
dp[i][1] = dp[i-1][1] + a[i][1]  // 第一列

---

📌 11. 过河卒 (P4844)

问题描述：棋盘上卒从A点到B点，避开马的控制点。

递推关系：

dp[i][j] = dp[i-1][j] + dp[i][j-1]  // 如果该点可达

注意事项：

• 马的控制点要标记为不可达
• 注意边界条件

---

📌 12. 矩阵求和 (P4851)

问题描述：矩阵相关的递推求和问题。

思路：二维前缀和或递推累积。

---

📌 13. 木瓜地 (P4840)

问题描述：类似的矩阵路径问题。

---

四、路径计数类递推

📌 14. 走出迷宫的方法数 (P4601) & 走出迷宫的方法数2 (P4602)

问题描述：计算从起点到终点的路径数量。

递推关系：

dp[i][j] = dp[i-1][j] + dp[i][j-1]  // 无障碍时

有障碍的情况：

if (grid[i][j] == 障碍) dp[i][j] = 0;
else dp[i][j] = dp[i-1][j] + dp[i][j-1];

---

递推解题模板

一维递推模板

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    // 1. 定义状态数组
    long long f[n+1];
    
    // 2. 确定初值
    f[1] = 1;
    f[2] = 2;  // 根据题目确定
    
    // 3. 递推计算
    for (int i = 3; i <= n; i++) {
        f[i] = f[i-1] + f[i-2];  // 递推关系
    }
    
    // 4. 输出结果
    cout << f[n] << endl;
    
    return 0;
}

二维递推模板

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    // 定义状态数组
    long long dp[n+1][m+1];
    int a[n+1][m+1];
    
    // 读取数据
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];
    
    // 初始化边界
    dp[1][1] = a[1][1];
    for (int i = 2; i <= n; i++) dp[i][1] = dp[i-1][1] + a[i][1];
    for (int j = 2; j <= m; j++) dp[1][j] = dp[1][j-1] + a[1][j];
    
    // 递推
    for (int i = 2; i <= n; i++) {
        for (int j = 2; j <= m; j++) {
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + a[i][j];
        }
    }
    
    cout << dp[n][m] << endl;
    
    return 0;
}

---

常见错误与技巧

⚠️ 常见错误

错误类型	说明	解决方案
数组越界	访问f[0]或f[n+1]	仔细检查边界
数据溢出	结果超过int范围	使用long long
初值错误	边界条件设置错误	手动验证小数据
递推方向错误	自顶向下还是自底向上	画图分析

✅ 技巧总结

1. 画表格推导：手工计算前几项，验证递推关系
2. 找规律：从简单情况开始，逐步推广
3. 逆向思维：有时候从后往前推更简单
4. 空间优化：如果只需要最后结果，可以用滚动数组

---

练习建议

📋 推荐练习顺序

阶段	题目	重点
入门	兔子繁殖、猴子吃桃	理解基本递推思想
基础	Pell数列、汉诺塔	掌握一维递推
进阶	铺地砖、骨牌铺方格	计数类递推
提高	数塔问题、摘花生	二维递推/DP入门
挑战	过河卒、走出迷宫	路径计数

📊 题目难度分布

入门 ★☆☆☆☆ : 兔子繁殖、猴子吃桃、汉诺塔
基础 ★★☆☆☆ : Pell数列、杨辉三角、平面分割
进阶 ★★★☆☆ : 铺地砖、骨牌铺方格、木瓜地
提高 ★★★★☆ : 数塔问题、摘花生、过河卒
挑战 ★★★★★ : 走出迷宫的方法数2、数塔的行走路径

---

📝 笔记总结

核心要点

1. 递推三要素：状态定义、递推关系、初始条件
2. 一维递推：注意递推方向和数据范围
3. 二维递推：注意边界初始化和遍历顺序
4. 计数问题：确定"最后一步"的选择方式

记忆口诀

递推问题不复杂，
状态关系要找对。
初值边界定清楚，
从小到大一步步。

---

🔗 相关资源

• OJ平台：bwloj.com
• 训练：竞赛向综合拔高2
• 题目编号：P4601-P4858

---

💡 提示：递推是动态规划的基础，掌握好递推思想对后续学习DP非常重要！