一、递推1.1 什么是递推递推从已知的初始条件出发按照一个固定的规律递推关系式一步步由前面的项推出后面的项直到得到所求结果。递推的两大要素缺一不可① 递推关系式状态转移方程描述 f(n) 与前面若干项的关系是题目的“规律”。② 初始条件边界值递推的起点如 f(1)1, f(2)1。没有它就无从算起。按推理方向递推又分为顺推由前推后最常见和逆推由已知的最后结果倒着往前推。1.2 顺推斐波那契家族原型斐波那契数列一对兔子从出生后第 3 个月起每个月都生一对兔子小兔子长到第三个月后每月又生一对……问第 n 个月有多少对兔子。当月兔子数 上月已有的都还在 上上月就有的这些这个月成熟、能生。递推式与边界f(n) f(n−1) f(n−2)f(1) 1f(2) 1数列0112358132134 ……核心代码顺推long long f[105]; f[1] f[2] 1; for (int i 3; i n; i) f[i] f[i-1] f[i-2]; cout f[n];变形一走楼梯 / 数楼梯P1255一次能跨 1 级或 2 级上到第 n 级的方法数最后一步要么跨 1 级前面在 n−1 级要么跨 2 级前面在 n−2 级。f(n) f(n−1) f(n−2) f(1) 1 f(2) 2 P1255 是高精度题n 最大可达 5000结果远超 long long必须用高精度加法数组 / string 模拟不能直接用整型递推。变形二蜜蜂路线P2437蜜蜂从编号 m 的蜂房爬到编号 n 的蜂房只能爬向编号更大的相邻蜂房。把起点平移成第 1 格问题与“走楼梯”完全相同距离为 n−m。f(i) f(i−1) f(i−2)同样因为数值巨大P2437 也需要高精度。变形三骨牌覆盖 / 覆盖墙壁2×n 骨牌覆盖用 2×1 骨牌铺满 2×n 的地板最左边若竖放一块剩下 2×(n−1)若横放两块剩下 2×(n−2)。f(n) f(n−1) f(n−2) f(1) 1 f(2) 2P1990 覆盖墙壁在 2×n 墙上铺 2×1 砖和 L 形砖方案数对10000 取模输出最后 4 位。除了上面的状态L 形砖会引入一个“凸出一格”的辅助状态需要两个递推数组联立设 f[i]恰好铺满 2×i 的方案数g[i]铺到“差一格未平”的方案数f[i] ( f[i−1] g[i−1] ) mod 10000g[i] ( 2·f[i−2] g[i−1] ) mod 10000✅ 方法提炼当一种状态说不清“铺了一半”的情况时就增加辅助状态。这是递推 / 动态规划里非常重要的技巧。变形四母牛繁殖一头母牛从出生后第 4 年起每年年初生一头小母牛不考虑死亡。f(n) f(n−1) f(n−3) f(1)1 f(2)2 f(3)3f(n−1) 是去年已有的牛f(n−3) 是三年前就存在、今年能生小牛的母牛数。1.3 逆推有些题目给出的是最后一天 / 最终状态要倒着推回最初这就是逆推法。关键是把顺推公式“反解”出来。猴子吃桃P5743猴子每天吃掉现有桃子的一半再多吃一个第 n 天只剩 1 个。设第 i 天有 f(i) 个则 f(i) 满足吃之前 − 一半 1 第二天的量即 f(i1) f(i)/2 − 1反解得到f(n) 1 f(i) 2 × ( f(i1) 1 ) 从第 n−1 天倒推到第 1 天long long x 1; // 最后一天 for (int i n - 1; i 1; i--) x 2 * (x 1); cout x;阿米巴繁殖阿米巴虫每过一代数量翻倍f(n) 2·f(n−1)。若已知若干代后的数量求之前某代反解为f(n−1) f(n) / 2✅ 顺推 vs 逆推怎么选看题目给的是“起点”还是“终点”。给起点就顺推给终点就把关系式反解后逆推。1.4 二维递推当状态由两个维度决定时如网格坐标、行与列就要用到二维递推通常写成表格从上到下、从左到右填。过河卒P1002——“二维斐波那契”卒从左上角 A(0,0) 走到 B(x,y)只能向下或向右走。到达某点的路径数 从上方来的 从左方来的。f(x,y) f(x−1,y) f(x,y−1)边界第一行、第一列只有 1 种走法 → f(0,y) f(x,0) 1但对方有一匹马马所在的点和它能一步跳到的9 个控制点都不能走。处理办法先用一个布尔数组 blocked 标记这 9 个点递推时遇到被挡的点就令其路径数为 0。for (int i 0; i nx; i) for (int j 0; j ny; j) { if (blocked[i][j]) { f[i][j] 0; continue; } if (i 0 j 0) f[i][j] 1; else { if (i 0) f[i][j] f[i-1][j]; if (j 0) f[i][j] f[i][j-1]; } }数字三角形P1216从三角形顶部走到最后一行每步只能走到左下方或右下方求路径上数字之和的最大值。设 f(i,j) 为走到第 i 行第 j 个位置时的最大和f(i,j) a(i,j) max( f(i−1,j−1), f(i−1,j) )也可以从下往上递推每个点加上它“左右两个孩子里更大的那个”最后顶部的值就是答案。杨辉三角每个数等于它“肩上”两个数之和a[i][j] a[i−1][j−1] a[i−1][j] a[1][1] 1每行首尾为 11.5 经典递推模型汇总模型递推式说明 / 对应题斐波那契f(n)f(n−1)f(n−2)走楼梯、蜜蜂路线、骨牌覆盖的共同骨架P1255 / P2437母牛繁殖f(n)f(n−1)f(n−3)成熟周期为 4 年汉诺塔h(n)2·h(n−1)1h(1)1移动次数呈 2n−1平面分割F(n)F(n−1)nn 条直线最多分平面数F(1)2卡特兰数C(n)Σ C(i)C(n−1−i)栈的输出序列、括号匹配P1044 栈过河卒f(x,y)f(x−1,y)f(x,y−1)二维计数注意挡点P1002放苹果见递归部分按“是否有空盘”分类P2386数的计算P1028与 栈P1044思路点拨试题分析这两题都是入门组经典的递推计数题核心在于找到“状态”和“状态转移”。P1028 数的计算是“前缀和优化递推”的典型P1044 栈则是“卡特兰数”的入门模型两者都要求先想清楚 f(n) 表示什么、由哪些更小的状态组合而来。P1028 数的计算设 f(n) 表示以 n 开头的合法数列个数。题目规定n 的左边可以再接一个不超过 n/2 的数接上的数又可以继续接。因此 f(n) 1 f(1) f(2) … f(n/2)其中“1”表示只有 n 自己这一种情况。直接按这个式子递推是 O(n²)用前缀和 s(n) s(n−1) f(n) 优化后f(n) 1 s(n/2)整体降到 O(n)。int f[1005], s[1005]; f[1] 1; s[1] 1; for (int i 2; i n; i) { f[i] 1 s[i / 2]; // 自己 所有不超过 i/2 的开头 s[i] s[i - 1] f[i]; } cout f[n];P1044 栈设 f(n) 表示 n 个元素依次进栈时可能的出栈序列总数。按“第一个出栈的元素”分类若第 1 个出栈的是第 k 个进栈的元素则它进栈前已有 k−1 个元素进栈并全部出栈f(k−1) 种它出栈后剩下 n−k 个元素继续f(n−k) 种。于是 f(n) Σ f(k−1)·f(n−k)k 从 1 到 n这就是卡特兰数。边界 f(0) f(1) 1。long long f[25] {1, 1}; // f[0] f[1] 1 for (int i 2; i n; i) for (int k 1; k i; k) f[i] f[k - 1] * f[i - k]; cout f[n];核心代码要点P1028 记得用前缀和避免超时P1044 的卡特兰数递推是双重循环注意 f(0) 要初始化为 1且 n 较小时结果在 long long 范围内。PART 02二、递归2.1 什么是递归生活中的例子电影院里你想知道自己坐第几排但太黑看不清于是问前面一排的人他也不知道、再问他前面……直到第一排的人确定“我是第 1 排”再一排排把答案传回来。这就是递归。递归一个函数在它的定义中直接或间接地调用自身。它把一个大问题不断缩小成结构相同的小问题直到小到可以直接回答边界条件。递归三要素① 递归边界什么时候停直接给出答案。没有边界会无限递归。② 递归范围每次调用都要让问题更接近边界规模变小。③ 递归式当前答案如何由更小问题的答案组合得到。递归代码模板返回类型 solve(参数) { if (到达边界) // 基准情形直接回答 return 基准值; else // 递归情形拆成更小的同类问题 return 用 solve(更小参数) 组合的结果; }阶乘P5739fac(n) n × fac(n−1) fac(0) 1long long fac(int n) { if (n 0) return 1; // 边界 return n * fac(n - 1); // 递归式 }2.2 递归的执行过程递推下去 回溯上来递归不是“一直往前走”而是有去有回分两个阶段递归下降阶段从求解目标出发不断调用更小的子问题从未知走向已知直到碰到边界。回溯上升阶段边界给出答案后一层层把结果返回、计算从已知回到未知最终得到原问题答案。以 fac(4) 为例fac(4) ├─ 要算 4 * fac(3) │ ├─ 要算 3 * fac(2) │ │ ├─ 要算 2 * fac(1) │ │ │ └─ fac(0)1 ← 触到边界开始回溯 │ │ └─ 返回 2*1 2 │ └─ 返回 3*2 6 └─ 返回 4*6 24 “在递归下去时做事”还是“在回溯上来时做事”写在递归调用之前的语句是下降阶段执行如先打印再递归写在递归调用之后的语句要等下层全部返回后才执行顺序正好相反——这是实现“逆序输出”的关键。2.3 递归经典应用① 字符串逆序输出 与 回文判断逆序输出先递归输出后面的子串再输出当前字符利用回溯阶段的逆序void revPrint(string s, int i) { if (i (int)s.size()) return; // 到末尾 revPrint(s, i 1); // 先处理后面 cout s[i]; // 回溯时才输出当前字符 }回文判断字符串是回文当且仅当首尾字符相同且去掉首尾后的子串也是回文递归到长度 ≤ 1 时成立。② 最大公约数 gcd辗转相除法gcd(a, b) gcd(b, a mod b) 当 b 0 时 gcd(a, 0) a③ 进制转换十进制 → 二进制除 2 取余但余数要倒着读正好用递归先递归处理 n/2回溯时再打印 n%2。void toBin(int n) { if (n 1) toBin(n / 2); cout n % 2; }④ 求 f(x,n)B2147 / B2148两题都是给出一个层层嵌套的数学表达式让你从最内层往外算。嵌套结构天然就是递归把“去掉最内层后的表达式”作为规模更小的同类问题边界是最内层的常数。直接照题目给出的嵌套定义写递归函数即可。试题分析B2147 与 B2148 的核心都是“嵌套表达式”。B2147 是基础版直接按题目给出的分段定义翻译成递归即可B2148 是进阶版嵌套层数更深、运算顺序更复杂需要仔细核对每一层的运算符与括号位置避免把“从内向外算”的顺序写错。核心代码B2147#include bits/stdc.h using namespace std; double f(double x, int n) { if (n 1) return x / (1 x); // 最内层边界 return x / (n f(x, n - 1)); // 从内向外逐层展开 } int main() { double x; int n; cin x n; cout fixed setprecision(2) f(x, n) endl; return 0; }核心代码B2148#include bits/stdc.h using namespace std; double f(double x, int n) { if (n 1) return x / (1 x); // 最内层边界 return x / (n f(x, n - 1)); // 注意运算顺序逐层向外 } int main() { double x; int n; cin x n; cout fixed setprecision(2) f(x, n) endl; return 0; }核心代码要点边界条件 n 1 时直接返回最内层结果递归式严格按题目给出的嵌套定义书写B2148 尤其要注意每一层分母中 n 与 f(x, n-1) 的先后顺序。两题都是给出一个层层嵌套的数学表达式让你从最内层往外算。嵌套结构天然就是递归把“去掉最内层后的表达式”作为规模更小的同类问题边界是最内层的常数。直接照题目给出的嵌套定义写递归函数即可。⑤ 阿克曼函数B2144Ackermann 函数是经典的双参数递归需要两个参数都正确处理边界与递推严格按题目给的分段定义翻译注意 m、n 分别何时归零。它增长极快测试数据的输入都很小。⑥ 幂次方P1010——递归分解把一个正整数表示成 2 的幂次之和并且指数本身也要继续这样表示如 131072 2(2(22(0))2(2)2)。思路对 n 先分解成若干个 2k再对每个指数 k 递归调用同样的分解函数。这是“递归处理、输出格式略繁琐”的代表题。核心代码P1010#include bits/stdc.h using namespace std; void solve(int n) { bool first true; // 控制加号输出 for (int k 15; k 0; k--) { // 2^15 20000从高次幂往下找 if (n (1 k)) { // n 含有 2^k 这一项 if (!first) cout ; // 非首项前输出加号 first false; if (k 0) cout 2(0); // 2^0 1 else if (k 1) cout 2; // 2^1 2指数 1 不再展开 else { cout 2(; // 指数 k 需要递归表示 solve(k); cout ); } } } } int main() { int n; cin n; solve(n); return 0; }核心代码要点从高到低枚举 n 的二进制位遇到 1 就输出对应的 2 的幂指数 k 大于 1 时递归调用 solve(k) 继续展开k 等于 0 或 1 时直接输出避免无限递归。⑦ 外星密码P1928——递归展开字符串形如 AC[3JA[2BC]] 的压缩串方括号表示把内部字符串重复若干次。读到 [ 时先读出数字重复次数再递归地解析方括号内部直到匹配的 ]把返回的串重复对应次数拼到答案里。✅ 识别信号凡是“括号嵌套、内层结构和外层完全一样”的题目解压、嵌套表达式、嵌套数据第一反应就是递归。⑧ 分形 / 分治递归赦免战俘、黑白棋子、Roads Around The FarmP5461 赦免战俘在 2n×2n 方阵中把左上角四分之一全部“赦免”置 0剩下三个小四分之一方阵重复同样操作直到边长为 1。用递归按四个象限处理即可可用位运算或下标判断。P1259 黑白棋子的移动按固定规则把棋子逐步移动到位每完成一大步后剩余棋子形成规模更小、结构相同的局面递归处理 n−1 的情况并按题目要求打印中间过程。P2907 Roads Around The Farm一群牛若数量能均分成两群、且两群数量差恰好为给定值就分成两群继续对每一群递归同样判断最后统计牛群总数。是典型的“能分就分”的分治递归。⑨ 放苹果P2386——分类递归把 i 个相同苹果放到 j 个相同盘子里允许空盘求不同分法数。按“有没有空盘”分成两类为避免重复只讨论“至少一个空盘”i j 时 f(i,j) f(i,i) 盘子比苹果多至多只用 i 个盘i ≥ j 时 f(i,j) f(i, j−1) f(i−j, j) 有空盘 / 每盘先放一个边界 f(i,1) 1 f(0,j) 12.4 记忆化搜索朴素递归最大的浪费是重复计算。以朴素递归求斐波那契为例f(5) 会反复展开f(3)、f(2) 被算很多遍节点数随 n 指数增长。记忆化搜索用一个数组 / map 把每个状态的答案存起来算之前先看“算过没有”算过就直接取用。long long memo[105]; long long fib(int n) { if (n 1 || n 2) return 1; if (memo[n] ! 0) return memo[n]; // 已算过直接取 return memo[n] fib(n - 1) fib(n - 2); // 算完存起来 }P1464 Function —— 记忆化模板题题目定义了一个三参数递归函数 w(a,b,c)规则较多含“只要有一个 ≤0”“只要有一个 20”等特殊分支且直接递归会有大量重复调用而超时。标准做法就是用三维数组记忆化每个三元组只算一次。这道题的价值在于训练“严格照题意写分支 用记忆化消除重复”。⚠️ 记忆化注意事项记忆数组要正确处理题目中“超过上限按上限算”的分支数组下标不能为负所以“≤0 直接返回”的判断要放在访问数组之前。2.5 递归的优缺点与优化方向优点代码贴近数学定义逻辑清晰、可读性强处理嵌套、分形、分治、回溯等问题时思路自然用记忆化后同样能达到很高效率。缺点每次调用都有函数调用开销朴素递归容易重复计算层数太深会栈溢出爆栈。 两种优化① 加记忆化解决重复计算递归写法不变只多一层缓存。② 递归改递推能列出递推式的直接用循环从小到大算彻底避免调用开销与爆栈通常是最优实现。PART 03三、DFS 枚举与回溯当问题需要“把所有可能的方案都尝试一遍”排列、组合、选择递归最常见的用法就是深度优先搜索DFS 回溯选定一个位置 → 递归处理后续 → 撤销选择换下一个。全排列P1706 / B3623——排列型枚举模板用一个数组 path 记录当前排列用 used[] 标记某数是否已用。每一层在当前位置枚举一个没用过的数选上后进入下一层递归返回时撤销标记。int path[15]; bool used[15]; void dfs(int pos, int n) { if (pos n 1) { // 凑满 n 个输出一个方案 for (int i 1; i n; i) cout setw(5) path[i]; cout \n; return; } for (int x 1; x n; x) if (!used[x]) { used[x] true; path[pos] x; // 选择 dfs(pos 1, n); used[x] false; // 撤销回溯 } }选数P1036——组合型枚举 判定从 n 个整数中选出 k 个判断它们的和是否为素数统计有多少种选法。用 DFS 按“选 / 不选”或“只往后选记录起点下标”枚举所有大小为 k 的组合求和后用试除法判素数。用“只往后选”可天然避免重复组合。状态空间搜索Mothers Milk 与 Walking HomeP1215 母亲的牛奶三个桶容量 A、B、C初始 A、B 空、C 满互相倒酒倒到源空或目标满为止。把每次倒酒后的“三桶酒量”看成一个状态DFS 枚举 6 种倒法用三维访问标记避免重复走当 A 桶为空时记录 C 桶的量排序输出。P7995 Walking Home在带障碍的网格中从左上走到右下限制“转弯次数”。DFS 带上“当前位置、当前方向、已转弯次数”等参数往下走并用记忆化 / DP 记录状态避免超时。核心代码P1215 母亲的牛奶#include bits/stdc.h using namespace std; int A, B, C; bool vis[25][25][25]; // 三维访问标记避免重复状态 setint ans; // 记录 A 桶为空时 C 桶的量 void dfs(int a, int b, int c) { if (vis[a][b][c]) return; // 已访问过直接返回 vis[a][b][c] true; if (a 0) ans.insert(c); // A 桶为空记录 C 桶的量 // 枚举 6 种倒法i 桶倒入 j 桶 int cap[3] {A, B, C}; int cur[3] {a, b, c}; for (int i 0; i 3; i) for (int j 0; j 3; j) { if (i j) continue; // 不能倒给自己 int pour min(cur[i], cap[j] - cur[j]); // 倒到源空或目标满 int nxt[3] {a, b, c}; nxt[i] - pour; nxt[j] pour; dfs(nxt[0], nxt[1], nxt[2]); } } int main() { cin A B C; dfs(0, 0, C); // 初始 A、B 空C 满 for (int x : ans) cout x ; return 0; }核心代码P7995 Walking Home#include bits/stdc.h using namespace std; int n, k, ans 0; char g[55][55]; int memo[55][55][4][4]; // 记忆化位置 方向 已转弯次数 int dx[4] {0, 1, 0, -1}; // 右、下、左、上 int dy[4] {1, 0, -1, 0}; void dfs(int x, int y, int dir, int turns) { if (turns k) return; // 转弯次数超限 if (x n - 1 y n - 1) { // 到达右下角 ans; return; } if (memo[x][y][dir][turns]) return; // 该状态已走过 memo[x][y][dir][turns] 1; for (int d 0; d 4; d) { int nx x dx[d], ny y dy[d]; if (nx 0 || nx n || ny 0 || ny n) continue; if (g[nx][ny] H) continue; // 障碍 int nt turns (d ! dir); // 方向改变则转弯次数 1 dfs(nx, ny, d, nt); } } int main() { cin n k; for (int i 0; i n; i) for (int j 0; j n; j) cin g[i][j]; dfs(0, 0, 0, 0); // 从左上角出发初始方向向右转弯 0 次 cout ans; return 0; }核心代码要点P1215 用三维 vis 数组标记三桶酒量状态枚举 6 种倒法A 桶为空时记录 C 桶量并排序输出P7995 用记忆化数组记录“位置 方向 转弯次数”避免重复搜索导致超时注意转弯次数超过限制时剪枝。Secret Cow CodeP3612——逆向定位避免真的展开字符串不断“复制自身并接到后面”形成超长串问第 k 个字符。直接展开会爆炸。关键是逆向找到 k 所在的那一次复制若 k 落在复制出的后半段就把它映射回原串对应的位置第一个复制字符对应原串最后一个字符k 不断缩小直到落回最初的字符串。这是“逆推 / 取模定位”思想的好题。 DFS 三件套状态参数当前在处理什么、边界得到一个完整方案、选择与撤销枚举并回溯。状态多、会重复时加访问数组或记忆化。PART 04四、26 题分层题单按学习路线分为5 组建议按顺序刷。每题可点击直达洛谷原题标签标注核心考点与注意事项。A 组 · 递归入门建立函数自调用直觉4 题01P5739 【深基7.例7】计算阶乘递归最基础的递归模板fac(n)n·fac(n−1)注意 fac(0)1。02B2142 求 123…N 的值递归用递归写累加练边界与返回也可对比循环写法。03B2144 阿克曼Ackermann函数双参数递归严格按分段定义翻译增长极快、输入很小。04P5743 【深基7.习8】猴子吃桃逆推由最后一天倒推f(i)2·(f(i1)1)。B 组 · 一维递推找递推式与初始值6 题05P1255 数楼梯高精度斐波那契型递推n 到 5000必须高精度加法。06P2437 蜜蜂路线高精度平移起点后同走楼梯同样需高精度。07P1028 [NOIP 2001 普及组] 数的计算递推前缀和f(n)1Σf(1..n/2)用前缀和优化。08P1044 [NOIP 2003 普及组] 栈卡特兰数栈输出序列数按第一个元素何时弹出分类。09P1990 覆盖墙壁取模辅助状态方案数对 10000 取模需 f、g 两状态联立。10P3612 [USACO17JAN] Secret Cow Code S逆推定位不展开超长串把位置 k 逆向映射回原串。C 组 · 二维递推表格上的状态转移2 题11P1002 [NOIP 2002 普及组] 过河卒题目描述棋盘上 A 点有一个过河卒需要走到目标 B 点。卒只能向下或向右走同时棋盘上有一匹马位于 C 点马所在的点和它能一步跳到的共 9 个点称为马的“控制点”卒不能经过这些点。给定 A、B、C 的坐标求卒从 A 走到 B 的路径总数。试题分析这是二维递推的经典题本质是“带障碍的网格路径计数”。设 f(x,y) 表示从 A 走到 (x,y) 的路径数则 f(x,y) f(x−1,y) f(x,y−1)边界为第一行、第一列只有 1 种走法。关键在于先用布尔数组标记马的 9 个控制点递推时遇到被挡的点令其路径数为 0。注意坐标从 0 开始且 A 点本身若被马控制也要特殊处理。核心代码#include bits/stdc.h using namespace std; long long f[25][25]; bool blocked[25][25]; int dx[9] {0, -2, -1, 1, 2, 2, 1, -1, -2}; int dy[9] {0, 1, 2, 2, 1, -1, -2, -2, -1}; int main() { int nx, ny, cx, cy; cin nx ny cx cy; for (int i 0; i 9; i) { int x cx dx[i], y cy dy[i]; if (x 0 x nx y 0 y ny) blocked[x][y] true; } for (int i 0; i nx; i) for (int j 0; j ny; j) { if (blocked[i][j]) { f[i][j] 0; continue; } if (i 0 j 0) f[i][j] 1; else { if (i 0) f[i][j] f[i-1][j]; if (j 0) f[i][j] f[i][j-1]; } } cout f[nx][ny]; return 0; }核心代码要点用 long long 存路径数防止溢出先标记 9 个控制点再递推递推时被挡点直接置 0起点 (0,0) 单独赋 1。12P1216 [IOI 1994 / USACO1.5] 数字三角形题目描述给定一个数字三角形从顶部出发每一步可以走到左下方或右下方一直走到最底层。求所有路径中经过数字之和的最大值。试题分析这是二维递推 / 动态规划的入门题。设 f(i,j) 为从顶部走到第 i 行第 j 个位置时的最大和则 f(i,j) a(i,j) max( f(i−1,j−1), f(i−1,j) )。更简洁的做法是从下往上递推每个点加上它“左右两个孩子里更大的那个”最后顶部的值就是答案省去边界判断。核心代码#include bits/stdc.h using namespace std; int a[1005][1005]; int main() { int n; cin n; for (int i 1; i n; i) for (int j 1; j i; j) cin a[i][j]; // 从下往上递推 for (int i n - 1; i 1; i--) for (int j 1; j i; j) a[i][j] max(a[i1][j], a[i1][j1]); cout a[1][1]; return 0; }核心代码要点从下往上递推时每个点取两个孩子中较大的那个累加最后 a[1][1] 即为答案也可自上而下递推但需注意边界处理。D 组 · 递归应用与记忆化嵌套 / 分治 / 分形8 题13B2147 求 f(x,n)题目描述给定实数 x 和正整数 n按如下嵌套公式求值f(x,n) x / (n f(x, n−1))其中 f(x,1) x / (1 x)。要求输出结果保留两位小数。试题分析嵌套递归按嵌套表达式从内向外照定义写递归。边界是 n 1 时直接返回最内层 x / (1 x)递归式严格照题目给出的嵌套定义书写即可。#include bits/stdc.h using namespace std; double f(double x, int n) { if (n 1) return x / (1 x); // 最内层边界 return x / (n f(x, n - 1)); // 从内向外逐层展开 } int main() { double x; int n; cin x n; cout fixed setprecision(2) f(x, n); return 0; }E 组 · DFS 枚举与综合拔高枚举所有方案 / 状态搜索6 题题目描述给定一个 n×n 的网格左上角为起点、右下角为终点网格中部分格子有障碍物H不能走。牛从左上角出发只能向右或向下走且全程最多只能转弯 k 次求从起点到终点的不同走法总数。试题分析P7995 是 DFS 与 DP 结合的综合题核心难点在于“转弯次数限制”。直接 DFS 会因重复搜索同一状态而超时因此需要把“当前位置 当前方向 已转弯次数”作为完整状态进行记忆化。搜索时若转弯次数超过 k 立即剪枝遇到障碍物跳过到达终点时计数。本题综合度较高是训练“状态设计 记忆化剪枝”的经典题目。核心代码P7995 Walking Home#include bits/stdc.h using namespace std; int n, k, ans 0; char g[55][55]; int memo[55][55][4][4]; // 记忆化位置 方向 已转弯次数 int dx[4] {0, 1, 0, -1}; // 右、下、左、上 int dy[4] {1, 0, -1, 0}; void dfs(int x, int y, int dir, int turns) { if (turns k) return; // 转弯次数超限 if (x n - 1 y n - 1) { // 到达右下角 ans; return; } if (memo[x][y][dir][turns]) return; // 该状态已走过 memo[x][y][dir][turns] 1; for (int d 0; d 4; d) { int nx x dx[d], ny y dy[d]; if (nx 0 || nx n || ny 0 || ny n) continue; if (g[nx][ny] H) continue; // 障碍 int nt turns (d ! dir); // 方向改变则转弯次数 1 dfs(nx, ny, d, nt); } } int main() { cin n k; for (int i 0; i n; i) for (int j 0; j n; j) cin g[i][j]; dfs(0, 0, 0, 0); // 从左上角出发初始方向向右转弯 0 次 cout ans; return 0; }核心代码要点用记忆化数组记录“位置 方向 转弯次数”避免重复搜索导致超时转弯次数超过 k 时立即剪枝遇到障碍物跳过到达终点时计数。注意初始方向设为向右且每次方向改变时转弯次数加 1。试题分析P7995 是 DFS 与 DP 结合的综合题核心难点在于“转弯次数限制”。直接 DFS 会因重复搜索同一状态而超时因此需要把“当前位置 当前方向 已转弯次数”作为完整状态进行记忆化。搜索时若转弯次数超过 k 立即剪枝遇到障碍物跳过到达终点时计数。本题综合度较高是训练“状态设计 记忆化剪枝”的经典题目。 刷题建议A→B→C→D→E 依次推进先独立写递推式 / 递归函数再看题解。P1255、P2437 务必亲手实现高精度P1464、P1215 重点体会“记忆化 / 访问标记”如何避免重复。PART 05五、易错点与自查清单递推常见错误只写递推式、漏了初始值循环下标从错误的位置开始越界或漏算结果会溢出却用 int / long long忘了高精度或取模取模题忘记每一步都取模或减法出现负数过河卒忘了处理挡点 / 边界行列。递归常见错误没有边界或边界写错 → 无限递归 / 段错误递归调用没有让规模变小朴素递归重复计算导致超时需记忆化递归过深爆栈改递推记忆数组下标可能为负越界访问。上考场前自查清单✅ 我能说出本题的状态f 表示什么吗✅ 我写出递推式 / 递归式并核对过下标含义吗✅初始值 / 边界都确定了吗✅ 看过数据范围了吗要不要高精度 / 取模取模值是多少✅ 递归会不会太深要不要改成递推或加记忆化✅ DFS 的访问标记 / 撤销写了吗会不会漏掉方案或重复计数✅ 用样例手推过一遍、并考虑了最小边界情况吗