P1002 [NOIP 2002 普及组] 过河卒：记忆化递归的思想与方法

1. 引言过河卒是 NOIP 2002 普及组的一道经典题目也是很多初学者接触动态规划与记忆化递归的第一道题。题目本身并不复杂但其中蕴含的「重复子问题」思想却是理解递归优化、动态规划乃至更高级算法的基础。本文不打算只给出一个能 AC 的代码而是想借这道题认真聊一聊记忆化递归Memoization背后的思考方式为什么朴素递归会超时记忆化到底「记」了什么它和递推动态规划又是什么关系2. 题目回顾2.1 题目描述棋盘上 A 点有一个过河卒需要走到目标 B 点。卒行走的规则可以向下、或者向右。同时在棋盘上的任一点有一个对方的马如下图该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此这匹马的控制点卒不能通过。棋盘用坐标表示A 点(0, 0)、B 点(n, m)n、m 为不超过 20 的整数同样马的位置坐标是需要给出的。现在要求你计算出卒从 A 点能够到达 B 点的路径条数。2.2 输入输出格式输入一行四个正整数分别表示 B 点坐标(n, m)和马的坐标(x, y)。输出一个整数表示从 A 到 B 的路径条数。2.3 样例输入6 6 3 3输出63. 朴素递归直观但低效3.1 递归的直觉卒只能向下或向右走那么从(i, j)到(n, m)的路径数自然可以拆成「从(i1, j)出发的路径数」加上「从(i, j1)出发的路径数」。写成递归就是intdfs(inti,intj){if(in||jm)return0;// 越界if(injm)return1;// 到达终点if(isControl(i,j))return0;// 马的控制点returndfs(i1,j)dfs(i,j1);// 向下 向右}这个写法非常符合直觉代码也极短。但它的时间复杂度是指数级的因为同一个状态(i, j)会被反复计算很多次。3.2 为什么慢重复子问题以(0, 0)出发为例dfs(1, 1)既会被dfs(0, 1)调用又会被dfs(1, 0)调用。随着棋盘变大这种重复会呈爆炸式增长。我们可以画一棵递归树来观察每个节点向下分裂出两个子节点树的高度约为n m因此节点总数约为2^(nm)。当n m 20时这个量级是天文数字必然超时。4. 记忆化递归把算过的结果存下来4.1 核心思想既然同一个状态会被重复计算那不如「算一次存起来下次直接用」。这就是记忆化递归——用空间换时间。具体做法开一个二维数组memo初始化为-1表示「还没算过」。每次进入dfs(i, j)时先查表如果已经算过直接返回缓存值否则计算并写入缓存。#includebits/stdc.husingnamespacestd;intn,m,x,y;longlongmemo[25][25];boolcontrol[25][25];boolisControl(inti,intj){returncontrol[i][j];}longlongdfs(inti,intj){if(in||jm)return0;if(injm)return1;if(isControl(i,j))return0;if(memo[i][j]!-1)returnmemo[i][j];// 命中缓存returnmemo[i][j]dfs(i1,j)dfs(i,j1);// 计算并缓存}intmain(){cinnmxy;memset(memo,-1,sizeof(memo));// 标记马的控制点intdx[]{1,1,-1,-1,2,2,-2,-2};intdy[]{2,-2,2,-2,1,-1,1,-1};control[x][y]true;for(intk0;k8;k){intnxxdx[k],nyydy[k];if(nx0nxnny0nym){control[nx][ny]true;}}coutdfs(0,0)endl;return0;}4.2 复杂度分析经过记忆化后每个状态(i, j)最多只计算一次状态总数约为(n1) × (m1)因此时间复杂度降为O(n × m)空间复杂度同样为O(n × m)。相比指数级的朴素递归这是质的飞跃。5. 记忆化递归 vs 递推动态规划5.1 两者的关系记忆化递归和递推自底向上的动态规划本质上是同一件事的两种写法记忆化递归自顶向下从大问题出发递归拆解到小问题用缓存避免重复。递推自底向上先算小问题再逐步组合成大问题。两者都依赖「最优子结构」和「重叠子问题」这两个性质区别只是计算顺序。5.2 各自的优缺点维度记忆化递归递推思考方式贴近自然递归容易写需要先想清楚状态转移顺序代码量通常更短有时更繁琐只算需要的状态是按需计算否可能算多余状态递归栈风险有深度大时可能爆栈无常数开销略大函数调用 查表更小对于过河卒这种状态转移方向非常明确的题目递推往往更简洁但对于状态转移关系复杂、难以确定计算顺序的题目记忆化递归往往更省心。5.3 递推写法参考#includebits/stdc.husingnamespacestd;intn,m,x,y;longlongdp[25][25];boolcontrol[25][25];intmain(){cinnmxy;intdx[]{1,1,-1,-1,2,2,-2,-2};intdy[]{2,-2,2,-2,1,-1,1,-1};control[x][y]true;for(intk0;k8;k){intnxxdx[k],nyydy[k];if(nx0nxnny0nym){control[nx][ny]true;}}dp[0][0]1;for(inti0;in;i){for(intj0;jm;j){if(control[i][j]){dp[i][j]0;continue;}if(i0)dp[i][j]dp[i-1][j];if(j0)dp[i][j]dp[i][j-1];}}coutdp[n][m]endl;return0;}6. 记忆化递归的通用套路从过河卒这道题我们可以提炼出记忆化递归的通用三步法定义状态明确dfs(i, j)表示什么参数要能唯一确定一个子问题。写出转移用自然递归的方式写出状态之间的关系。加缓存在递归入口先查缓存计算后写入缓存。这个套路几乎适用于所有「递归会重复计算」的问题比如斐波那契数列、爬楼梯、数字三角形、背包问题等。掌握了它你就掌握了一把处理重叠子问题的通用钥匙。7. 总结过河卒虽然是一道入门题但它完美地展示了记忆化递归的核心价值识别重复子问题并用缓存消除重复计算。朴素递归直观但指数级超时记忆化递归用空间换时间把复杂度降到多项式级记忆化递归与递推是同一思想的正反两面各有适用场景。希望这篇文章能帮你真正理解记忆化递归的「为什么」和「怎么做」。下次再遇到递归超时不妨先想一想是不是有重复子问题能不能用一张表把它记下来