登录以参加训练计划

递推算法详解及其应用

深入解析递推算法的原理、实现及其在CSP-J竞赛中的应用

目录

1. 递推算法基本概念
2. 递推关系建立方法
3. 一维递推经典问题
4. 二维递推经典问题
5. 递推优化技巧
6. 综合应用实例

---

1. 递推算法基本概念

什么是递推算法

递推是一种通过已知条件推导未知结果的算法思想，核心是找到问题中相邻项之间的关系（递推关系），然后从初始条件出发逐步计算出后续结果。

graph LR
A[初始状态] --> B[递推关系]
B --> C[状态1]
C --> D[状态2]
D --> E[...]
E --> F[最终结果]

递推三要素

1. 初始条件：问题的最基本情况
2. 递推关系：状态转移方程
3. 边界条件：递推终止条件

递推 vs 递归

特性	递推	递归
实现方式	循环迭代	函数自调用
方向	自底向上	自顶向下
效率	高效，无函数调用开销	较低，有重复计算
内存	占用较少	栈空间消耗大
适用场景	线性问题、状态转移	树形结构、分治问题

---

2. 递推关系建立方法

递推关系建立步骤

1. 分析问题：理解问题本质
2. 定义状态：明确dp[i]的含义
3. 寻找关系：建立dp[i]与dp[i-1]等的联系
4. 确定边界：设置dp[0], dp[1]等初始值

常见递推关系类型

类型	递推关系	典型问题
线性递推	dp[i] = adp[i-1] + bdp[i-2]	斐波那契数列
前缀和递推	sum[i] = sum[i-1] + a[i]	区间求和
二维递推	dp[i][j] = f(dp[i-1][j], dp[i][j-1])	网格路径
状态压缩递推	dp[i][state] = f(prev states)	TSP问题

---

3. 一维递推经典问题

3.1 斐波那契数列

问题描述：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)

#include <iostream>
using namespace std;

const int MAXN = 100;
long long fib[MAXN] = {0, 1}; // 初始条件

int main() {
    int n = 50;
    
    // 递推计算
    for (int i = 2; i <= n; i++) {
        fib[i] = fib[i-1] + fib[i-2]; // 递推关系
    }
    
    cout << "斐波那契数列第" << n << "项: " << fib[n] << endl;
    return 0;
}

3.2 爬楼梯问题

问题描述：每次爬1或2阶，n阶楼梯有多少种爬法

#include <iostream>
using namespace std;

const int MAXN = 100;
int dp[MAXN] = {1, 1}; // dp[0]=1, dp[1]=1

int main() {
    int n = 10;
    
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2]; // 递推关系
    }
    
    cout << n << "阶楼梯有" << dp[n] << "种爬法" << endl;
    return 0;
}

3.3 错位排列（错排问题）

问题描述：n个元素的排列中，所有元素都不在自己原位置的排列数

#include <iostream>
using namespace std;

const int MAXN = 100;
long long derangement[MAXN] = {0, 0, 1}; // d[0]=0, d[1]=0, d[2]=1

int main() {
    int n = 5;
    
    for (int i = 3; i <= n; i++) {
        derangement[i] = (i-1) * (derangement[i-1] + derangement[i-2]);
    }
    
    cout << n << "个元素的错排数: " << derangement[n] << endl;
    return 0;
}