递推算法通过已知的初始条件和递推关系逐步推导出后续结果。与递归不同递推通常使用循环结构实现避免了函数调用的开销效率更高。本文将用C语言通过几个经典例题详细讲解递推算法的思想和实现。一、递推算法基本思想递推算法的核心是递推关系式和初始条件。递推关系式描述了当前状态如何由前一个或多个状态推导而来而初始条件则是递推的起点。在C中实现递推通常遵循以下步骤定义状态数组使用数组存储中间结果设置初始条件根据问题初始化数组的前几项建立递推关系通过循环按照递推公式计算后续项输出结果返回或输出目标位置的值递推与递归的主要区别在于递推是自底向上的迭代过程而递归是自顶向下的函数调用过程。递推通常更高效适合处理线性结构问题。二、一维递推问题1. 斐波那契数列问题描述斐波那契数列的第1项为1第2项为1从第3项开始每一项都等于前两项之和。递推关系f[i] f[i-1] f[i-2]初始条件f[1] 1, f[2] 1C代码实现12345678910111213141516171819202122#include iostreamusingnamespacestd;intmain() {intn;cin n;// 定义数组存储斐波那契数假设n不超过45保证在int范围内intf[46];// 第45项约为1.13e9仍在int范围内// 初始化初始条件f[1] 1;f[2] 1;// 递推计算for(inti 3; i n; i) {f[i] f[i-1] f[i-2];}cout f[n] endl;return0;}代码解析数组f存储已计算的结果避免重复计算循环从3开始依次计算每一项当n≤45时结果在int范围内约21亿内2. 爬楼梯问题问题描述有n阶楼梯每次可以爬1阶或2阶问有多少种不同的爬法。递推分析设a[i]表示爬到第i阶楼梯的方法数。由于每次只能爬1阶或2阶所以到达第i阶只能从第i-1阶爬1阶或从第i-2阶爬2阶。递推关系a[i] a[i-1] a[i-2]初始条件a[1] 1爬1阶只有1种方法a[2] 2爬2阶有2种方法C代码实现123456789101112131415161718#include iostreamusingnamespacestd;intmain() {intn;cin n;inta[46];// 假设n不超过45a[1] 1;a[2] 2;for(inti 3; i n; i) {a[i] a[i-1] a[i-2];}cout a[n] endl;return0;}代码解析这个问题实质上是斐波那契数列的变体只是初始条件不同三、二维递推问题1. 无障碍网格路径计数问题描述在一个m×n的网格中从左上角(1,1)出发每次只能向右或向下移动一步要到达右下角(m,n)问有多少条不同的路径。递推分析设b[i][j]表示从起点到达坐标(i,j)的路径数。由于只能向右或向下移动要到达(i,j)只能从上方(i-1,j)或左方(i,j-1)过来。递推关系b[i][j] b[i-1][j] b[i][j-1]边界条件第一行和第一列的所有位置都只有1条路径C代码实现123456789101112131415161718192021222324#include iostreamusingnamespacestd;intmain() {intm, n;cin m n;// 使用二维数组假设m和n不超过20intb[21] {0};// 初始化第一行和第一列b[1][1] 1;// 递推计算for(inti 1; i m; i) {for(intj 1; j n; j) {if(i 1 j 1)continue;// (1,1)点是初始化条件不用递推b[i][j] b[i-1][j] b[i][j-1];}}cout b[m][n] endl;return0;}代码解析数组b[i][j]表示到达(i,j)的路径数初始化第一行和第一列为1因为沿着边线只有一条路径双重循环从(2,2)开始递推计算2. 有障碍网格路径计数路径计数2洛谷P1176问题描述一个 N×N 的网格你一开始在 (1,1)即左上角。每次只能移动到下方相邻的格子或者右方相邻的格子问到达 (N,N)即右下角有多少种方法。但是这个问题太简单了所以现在有 M 个格子上有障碍即不能走到这 M 个格子上。递推分析递推关系与无障碍情况类似但需要额外考虑障碍物如果(i,j)是障碍物则b[i][j] true否则a[i][j] a[i-1][j] a[i][j-1]C代码实现12345678910111213141516171819202122232425262728293031323334#include iostreamusingnamespacestd;constintMOD 100003;// 定义模数常量避免魔法数字inta[1001][1001] {0};// 显式初始化为0boolb[1001][1001] {false};// 显式初始化为falseintmain() {intn, m;cin n m;// 读入障碍物for(inti 1; i m; i) {intx, y;cin x y;b[x][y] true;}// 初始化起点a[1][1] 1;// 递推for(inti 1; i n; i) {for(intj 1; j n; j) {// 跳过起点和障碍物if(i 1 j 1)continue;if(b[i][j])continue;a[i][j] (a[i-1][j] a[i][j-1]) % MOD;}}cout a[n][n] endl;return0;}四、马走日过河卒问题问题描述棋盘上有一个卒需要从A点(1,1)走到B点(n,m)卒只能向右或向下移动。棋盘上有一个马马走日字马所在位置及其控制点马能走到的8个位置卒不能通过。递推分析这是网格路径计数问题的变体增加了障碍点马的控制点。设b[i][j]表示卒从起点到达(i,j)的路径数stop[i][j]表示(i,j)是否为障碍点。递推关系与有障碍网格类似如果(i,j)是障碍点则b[i][j] 0否则b[i][j] b[i-1][j] b[i][j-1]C代码实现123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#includebits/stdc.husingnamespacestd;// 定义 long long 类型别名用于存储可能的大数结果#define ll long long// 马的控制点方向数组包括马本身及其8个走日位置共9个方向// dx和dy分别对应行和列的变化量其中(0,0)表示马自身位置intdx[] {-2, -2, -1, -1, 0, 1, 1, 2, 2};intdy[] {-1, 1, -2, 2, 0, -2, 2, -1, 1};// 标记数组s[i][j]true表示(i,j)是障碍点马的控制点bools[40];// 动态规划数组ans[i][j]表示从起点到达(i,j)的路径数ll ans[40];// 变量定义bx,by为目标点坐标mx,my为马的位置坐标intbx, by, mx, my;intmain() {// 读入目标点坐标和马的位置坐标原始坐标从(0,0)开始cin bx by mx my;// 所有坐标加2偏移操作防止后续计算马的控制点时数组越界// 这样棋盘有效坐标从(2,2)开始对应原坐标(0,0)bx2, by2, mx2, my2;// 标记马的控制点为障碍包括马自身// dx和dy数组长度为9索引0~8for(inti 0; i 9; i) {s[mxdx[i]][mydy[i]] true;}// 递推初始化起点(2,2)的路径数为1ans[2][2] 1;// 递推遍历从起点到目标点的所有位置for(inti 2; i bx; i) {for(intj 2; j by; j) {// 如果当前位置是障碍点或是起点则跳过起点已初始化if(s[i][j] || i2j2)continue;// 状态转移方程到达(i,j)的路径数等于从左边(i,j-1)和从上方(i-1,j)的路径数之和// 由于卒只能向右或向下移动因此只需考虑这两个方向ans[i][j] ans[i][j-1] ans[i-1][j];}}// 输出结果到达目标点(bx,by)的路径数cout ans[bx][by];return0;}五、递推算法的核心要点1. 确定递推状态递推状态是问题的关键通常用一个或多个变量表示问题的某个状态。例如爬楼梯问题a[i]表示到达第i阶的方法数网格路径问题b[i][j]表示到达(i,j)的路径数状态的定义需要能够完整描述问题的当前情况并且能够通过递推关系转移到其他状态。2. 建立递推关系递推关系描述了状态之间的转移方式通常基于问题的限制条件。例如爬楼梯一次只能爬1或2阶 →a[i] a[i-1] a[i-2]网格路径只能向右或向下 →b[i][j] b[i-1][j] b[i][j-1]3. 设置初始条件初始条件是递推的起点必须明确给出。例如爬楼梯a[1] 1, a[2] 2网格路径第一行和第一列都为1无障碍时