1. 从“踩方格”看递推算法的本质第一次接触踩方格这道题时我被它简洁的描述和巧妙的解法深深吸引。题目看似简单在一个无限大的方格矩阵上行走每次只能向北、东、西三个方向移动且不能重复走过同一个格子。问走n步有多少种不同的方案。但正是这种表面简单实则内涵丰富的题目最能锻炼我们的算法思维。让我们先理解题目的限制条件。不能重复走同一个格子意味着路径不能交叉只能向北、东、西三个方向移动则限制了每一步的选择。这种受限网格行走问题在信息学奥赛中非常常见比如机器人走迷宫、棋盘上的马步问题等。我最初尝试用递归暴力求解很快就发现当n15时程序就跑不动了。这时才意识到需要更高效的算法——递推。递推的核心思想是把大问题分解为小问题利用已知的小问题解来推导大问题的解。在踩方格中当前步的方案数取决于前几步的状态。2. 两种递推思路的对比分析2.1 状态合并法第一种解法将问题简化为一个递推公式a[i] a[i-1]*2 a[i-2]。这个公式怎么来的呢经过多次尝试和验证我发现如果上一步是向东或向西走的那么当前步可以有2种选择不能往回走如果上一步是向北走的那么当前步有3种选择而上一步向北走的方案数恰好等于大上一步的所有方案数这种思路的优点是代码极其简洁只需要一个一维数组就能解决问题。我在实际编码时发现当n20时结果已经很大超过100万所以要用long long类型存储。#include bits/stdc.h using namespace std; long long a[25]; int main() { int n; cin n; a[1] 3; a[2] 7; for(int i3; in; i) a[i] a[i-1]*2 a[i-2]; cout a[n]; return 0; }2.2 状态分离法第二种解法将状态分为两类a[i]表示第i步向北走的方案数b[i]表示第i步向东或向西走的方案数。递推关系变为当前步向北走的方案数 上一步所有方案数因为从任何方向都可以转向北当前步向东/西走的方案数 上一步向北的方案数×2 上一步向东/西的方案数×1#include bits/stdc.h using namespace std; long long a[25], b[25]; // a:北, b:东西 int main() { int n; cin n; a[1]1; b[1]2; for(int i2; in; i) { a[i] a[i-1] b[i-1]; b[i] 2*a[i-1] b[i-1]; } cout a[n] b[n]; return 0; }这两种方法看似不同实则本质相通。第一种是第二种的数学合并第二种则更直观地反映了状态转移的过程。在实际比赛中我建议先用第二种方法理清思路再考虑是否能优化为第一种形式。3. 递推模型的通用解题框架通过踩方格问题我们可以总结出一个解决递推问题的通用框架定义状态明确要记录什么信息。在踩方格中就是每一步的方案数。确定边界条件小规模情况的解。n1时有3种走法n2时有7种。建立状态转移方程当前状态如何由之前状态推导而来。选择实现方式根据问题特点决定用递归、记忆化搜索还是迭代递推。优化空间复杂度如果可能用滚动数组减少空间使用。这个框架适用于绝大多数递推问题。比如经典的斐波那契数列、爬楼梯问题都可以套用这个模式。在实际比赛中我经常遇到选手卡在状态定义这一步。我的经验是先考虑最简单粗暴的状态表示再逐步优化。比如踩方格可以先记录每一步的坐标和方向再发现其实只需要分类记录方向即可。4. 路径计数模型的扩展应用踩方格问题其实是一个典型的路径计数模型这种模型在算法竞赛中有着广泛的应用场景。让我们看几个变种4.1 带障碍物的网格行走假设方格中某些格子有障碍物不能通过这时我们的状态就需要增加位置信息。通常用dp[i][j]表示走到(i,j)的方案数状态转移要考虑从哪些相邻格子可以到达当前格子。// 假设grid[i][j]1表示障碍物 int dp[MAX][MAX] {0}; dp[0][0] 1; for(int i0; in; i) { for(int j0; jm; j) { if(grid[i][j]) continue; if(i0) dp[i][j] dp[i-1][j]; if(j0) dp[i][j] dp[i][j-1]; } }4.2 有限方向移动类似于踩方格但移动方向可能更多或更少。比如象棋中马的移动日字形或者机器人只能向右或向下移动。这类问题的关键是准确描述所有可能的转移方式。4.3 带有额外限制的路径比如路径不能自交、必须经过某些关键点、在特定步数达到特定位置等。这类问题通常需要在状态中增加额外维度来记录这些限制条件。我在一次比赛中遇到过这样一个题目在n×m网格中从左上到右下只能向右或向下移动且路径上所有格子的数字之和不能超过k。这需要在状态中增加一维记录当前和dp[i][j][s]表示走到(i,j)时和为s的方案数。5. 递推算法的优化技巧当问题规模变大时我们需要考虑递推算法的优化。这里分享几个实用技巧5.1 滚动数组优化观察踩方格的第一种解法发现计算a[i]只需要a[i-1]和a[i-2]因此可以用三个变量代替整个数组long long solve(int n) { if(n 1) return 3; if(n 2) return 7; long long a 3, b 7, c; for(int i3; in; i) { c 2*b a; a b; b c; } return b; }这样空间复杂度从O(n)降到了O(1)对于n很大的情况特别有用。5.2 矩阵快速幂对于线性递推式我们可以用矩阵快速幂将时间复杂度从O(n)降到O(logn)。以踩方格为例递推式a[n]2a[n-1]a[n-2]可以表示为| a[n] | | 2 1 | | a[n-1] | | a[n-1] | | 1 0 | × | a[n-2] |这样我们就可以用快速幂来计算这个矩阵的(n-2)次方从而快速求得a[n]。5.3 预处理与记忆化对于一些输入范围固定的问题可以预先计算所有可能的结果这样处理查询时只需要O(1)时间。这在比赛中有时限要求时特别有用。6. 常见错误与调试技巧在实现递推算法时新手常会遇到一些典型错误。根据我的经验最常见的有边界条件错误比如忘记处理n0或n1的情况。在踩方格中如果n1时返回错误值后续所有计算都会出错。初始化不完整只初始化了部分边界条件。比如在第二种解法中如果忘记初始化b[1]2整个结果就会错误。整数溢出没有使用足够大的数据类型。当n20时结果已经是很大的数必须用long long。循环范围错误比如循环从i1开始但访问了a[i-2]导致数组越界。调试这类问题时我通常采用以下方法打印中间结果在循环中输出每一步的计算值看是否符合预期。小数据测试先用小的n值手动计算与程序输出对比。边界测试特别测试n0,1,2等小值和大值的情况。记得在一次比赛中我因为把a[2]初始化为5而不是7导致整个题目没做出来。从那以后我都会特别仔细地验证边界条件。