1. 问题引入从“未名湖边的烦恼”到经典递归模型最近在整理蓝桥杯的历年练习题翻到了ALGO-122这道题题目名字挺有意思叫“未名湖边的烦恼”。乍一看还以为是什么校园情感故事其实是一道非常经典的算法问题核心是计算合法的出栈序列数量或者更广义地说是卡特兰数Catalan Number的一个经典应用场景。很多朋友第一次接触递归或者动态规划时可能都在“上台阶”、“斐波那契数列”上打转而这道题提供了一个更生动、也更需要动点脑筋的模型。题目的描述大概是这样的冬天到了未名湖上结了冰上面有两种人租借冰鞋的人和还冰鞋的人。租鞋处没有库存所有的冰鞋都借出去了。现在有m个人来还鞋n个人来借鞋。工作人员需要安排他们排成一队逐个处理。但是有一个硬性规定在任何时刻队伍中准备还鞋的人数都不能少于准备借鞋的人数。问一共有多少种可能的排队顺序举个例子如果m2还鞋n1借鞋。我们用R表示还鞋L表示借鞋。合法的序列有RRL, RLR。只有两种。如果mn2合法的序列有RRLL, RLRL, RLRR?不对最后一个R后L比R多非法。我们来枚举一下RRLL, RLRR? 等等我们需要系统的方法。这其实就是经典的“括号匹配”问题把“还鞋”看成左括号(“借鞋”看成右括号“)”要求在任何前缀中左括号的数量不少于右括号的数量。求合法的括号序列总数。这个数就是卡特兰数 C(m, n) 的一个特例当mn时。所以这道“烦恼”的本质是让我们计算一个组合数学的值。它考察的不仅仅是编码能力更是对问题模型的抽象和转化能力。下面我们就从最朴素的思路开始一步步拆解这道题并探讨其背后的多种解法以及在实际解题中容易踩的坑。2. 问题抽象与数学建模从生活场景到卡特兰数首先我们需要把生活化的描述转化为严谨的数学或计算机模型。这是解决算法问题的第一步也是最关键的一步。2.1 模型建立设还鞋人数为m借鞋人数为n。 我们用一个长度为mn的序列来表示排队顺序序列中包含m个 ‘R’ (Return) 和n个 ‘L’ (Lend)。 约束条件对于序列的任何一个前缀从开头到任意位置的子序列其中 ‘R’ 的数量必须大于等于 ‘L’ 的数量。 初始状态工作人员手上有0双鞋。第一个人必须是还鞋的‘R’否则借鞋的人无鞋可借序列非法。 最终状态处理完所有人后借出的鞋应全部归还所以最终 ‘R’ 和 ‘L’ 的数量相等吗不最终状态是鞋子全部借出又全部归还所以最终工作人员手上的鞋数应为0。这意味着在整个序列中m必须等于n吗仔细审题租借处没有库存所有鞋已借出。有m个人来还n个人来借。最终鞋应该全部在借出状态吗不是最终应该是收支平衡。初始库存为0还了m双借了n双最终库存是m - n。但题目没有说最终要清空库存只是要求处理过程中不能出现“想借但没鞋”的情况。然而一个合理的隐含条件是排队结束后不应该有人没处理完也不应该留下无限的鞋。通常这类问题如栈操作都默认m n且最终栈为空即鞋的净库存为0。但题目描述并未明确要求mn。我们看看样例和常规模型经典的“括号匹配”问题要求左右括号数相等即mn。如果m n那么最终会有m-n双鞋留在租借处这也是可能的。但约束条件“任何时刻还鞋人数不少于借鞋人数”依然成立。所以模型更通用求由m个R和n个L组成的、满足任意前缀中#R #L的序列总数。其中m n。2.2 与卡特兰数的关联当m n时这就是经典的卡特兰数问题。第n个卡特兰数C_n的公式是C_n (1/(n1)) * C(2n, n)其中C(2n, n)是组合数。 它表示n对括号的合法序列数或者n个元素的出栈序列数。对于更一般的m和n(m n)这个问题等价于从网格左下角(0,0)走到右上角(m, n)每次只能向右R或向上L走一步且路径不允许穿过对角线y x但可以接触。这里向右走代表还鞋R向上走代表借鞋L。约束条件“前缀中R不少于L”翻译成坐标就是路径始终在直线y x下方包括线上。因为当走了a步向右b步向上时当前坐标是(a, b)条件a b即b a也就是点在对角线下方。那么从(0,0)到(m, n)且不穿过对角线yx的路径数是多少这是一个经典的组合问题可以用反射法André‘s reflection method或者动态规划求解。其答案为C(mn, n) - C(mn, n-1)其中C(a,b)是组合数。当mn时化简后就是卡特兰数公式。因此我们的目标就是计算这个值f(m, n) C(mn, n) - C(mn, n-1)其中规定当n0时C(mn, n-1)0且m n。3. 核心算法思路递归、动态规划与数学公式的抉择有了数学模型接下来就是如何用代码实现计算。通常有三种主流思路递归搜索、动态规划记忆化搜索、直接组合数学公式计算。每种方法各有优劣适用于不同的场景和约束条件。3.1 递归搜索DFS 剪枝这是最直观也最能体现问题本质的方法。我们模拟整个排队过程用一个递归函数dfs(return_num, lend_num)来表示当前剩余return_num个R和lend_num个L可供排列并且在此刻之前已经排好的序列满足约束即之前的R不少于L。那么下一步可以做什么如果return_num 0我们可以放一个R。这总是合法的因为放R会增加R的累计数量使得“R不少于L”的条件更可能满足。如果lend_num 0并且当前已经排好的序列中R的数量大于L的数量即累计R 累计L我们可以放一个L。放L的前提是确保放了之后前缀中R仍然不少于L。由于我们是从合法状态递归下来的所以只需要检查“当前剩余”之前的累计状态。更巧妙的做法是我们不在参数里维护累计值而是维护“当前库存”的概念。我们可以换一个角度设stock为当前租借处库存的鞋数。初始stock 0。如果来一个还鞋的(R)stock加1。如果来一个借鞋的(L)stock减1。 约束条件任何时刻stock 0因为如果stock 0意味着借鞋时没鞋可借。 目标用光所有m个R和n个L求有多少种顺序能使stock始终非负。这样递归函数可以定义为dfs(r, l, stock)表示剩余r个Rl个L当前库存为stock。那么若r 0我们可以选择R新的状态是dfs(r-1, l, stock1)。这个选择总是可行的。若l 0 且 stock 0我们可以选择L新的状态是dfs(r, l-1, stock-1)。这里stock 0确保了借鞋后库存不会变成负数。递归边界当r 0 且 l 0时找到一种合法排列返回1。否则返回两种选择之和。这种递归的代码非常简洁但时间复杂度是指数级的大约为O(2^(mn))。对于m, n较小的情况比如不超过20勉强可以接受。但蓝桥杯的测试数据可能会比较大这就需要优化。3.2 记忆化搜索递归 缓存递归搜索中有大量重复的子状态。例如dfs(2,2,0)可能会通过不同路径再次计算dfs(1,2,1)。我们可以用一个三维数组dp[r][l][stock]来缓存已经计算过的结果这就是记忆化搜索本质上是自顶向下的动态规划。状态定义dp[r][l][s]表示剩余r个Rl个L当前库存为s时能形成的合法序列数。 状态转移dp[r][l][s] 0(初始值) 若r 0dp[r][l][s] dp[r-1][l][s1]若l 0 且 s 0dp[r][l][s] dp[r][l-1][s-1]边界dp[0][0][s] 1(当r和l都为0时无论s是多少已经形成一种序列但通常s也应为0才合理不过根据定义当rl0时只有一种情况就是结束所以返回1)。这里有一个细节stock的最大值是多少最坏情况是先把所有R都还了stock最大为m。所以stock的维度需要开到m1。记忆化搜索将时间复杂度优化到了状态数级别即O(m * n * m)对于m, n在几百以内的情况完全可以接受。3.3 动态规划递推我们可以将记忆化搜索转化为自底向上的递推。定义二维数组dp[i][j]为一个更精简的状态表示已经使用了i 个R和 j 个L且满足约束的方案数。注意这里“已经使用”和前面的“剩余”是互补的。那么dp[i][j]可以从哪里转移而来 要形成(i, j)的状态最后一个人要么是R要么是L。如果最后一个人是R那么在此之前的状态是(i-1, j)。只要(i-1, j)状态是合法的再加上一个R肯定合法因为R只会增加库存。所以dp[i][j] dp[i-1][j]。如果最后一个人是L那么在此之前的状态是(i, j-1)。但是加上一个L后要保证合法就要求在(i, j-1)状态时库存至少为1即R比L至少多1。如何用i和j表示库存库存就是i - j使用的R减去使用的L。所以在(i, j-1)状态时库存为i - (j-1) i - j 1。要求这个值 1即i - j 1 1i j。这不就是我们的约束条件吗在(i, j-1)状态时本身就要求i j-1。但为了能放L需要更强的条件i j-1即i j。所以当i j时可以从dp[i][j-1]转移过来。因此动态转移方程为dp[i][j] dp[i-1][j] dp[i][j-1]其中i j。 边界条件dp[0][0] 1。并且对于所有i j的情况dp[i][j] 0。 最终答案就是dp[m][n]。这个二维DP的时间复杂度为O(m * n)空间复杂度可以用滚动数组优化到O(n)非常高效。3.4 组合数学公式法如果我们已经推导出了公式f(m, n) C(mn, n) - C(mn, n-1)那么问题就转化为如何高效、准确地计算大组合数。这里有几个难点数值范围m和n可能很大比如达到几百甚至上千那么mn会更大直接计算阶乘会溢出。取模问题题目通常要求输出具体数值不取模这意味着我们需要处理大整数运算。对于蓝桥杯这样的竞赛m, n的范围通常不会太大比如1 m, n 20直接用long long计算组合数可能就够了。计算组合数C(a, b)有多种方法利用公式C(a, b) a! / (b! * (a-b)!)。预先计算阶乘但要注意溢出。利用递推公式杨辉三角C(a, b) C(a-1, b-1) C(a-1, b)并打表。这对于a, b较小的情况很方便。利用乘法公式逐步计算C(a, b) (a/b) * C(a-1, b-1)循环计算。如果数据范围更大需要高精度运算那就比较复杂了。在竞赛中如果时间充裕用高精度库或者自己实现大数乘除法也是可以的。但更常见的做法是题目会设计好数据范围使得用long long或unsigned long long可以存下。4. 代码实现与细节剖析从理论到AC代码理论分析得再透彻最终还是要落到代码上。这里我分别用递归DFS、记忆化搜索、动态规划和公式法四种方式实现并对比它们的优劣和适用场景。我们假设题目输入为两个整数m和nm n输出方案数。4.1 递归搜索实现#include stdio.h long long dfs(int r, int l, int stock) { if (r 0 l 0) { return 1; // 所有人处理完毕找到一种合法序列 } long long ans 0; if (r 0) { // 选择还鞋 ans dfs(r - 1, l, stock 1); } if (l 0 stock 0) { // 选择借鞋前提是当前有鞋可借 ans dfs(r, l - 1, stock - 1); } return ans; } int main() { int m, n; scanf(%d %d, m, n); // 初始库存为0有m个Rn个L printf(%lld\n, dfs(m, n, 0)); return 0; }注意这个纯递归版本在mn10时可能就需要几秒时间了因为状态数爆炸。仅适用于理解思路或极小数据。4.2 记忆化搜索实现#include stdio.h #include string.h #define MAX_M 20 // 假设最大范围 #define MAX_N 20 long long memo[MAX_M 1][MAX_N 1][MAX_M 1]; // 第三维是stock最大为m long long dfs_memo(int r, int l, int stock) { if (r 0 l 0) { return 1; } if (memo[r][l][stock] ! -1) { return memo[r][l][stock]; } long long ans 0; if (r 0) { ans dfs_memo(r - 1, l, stock 1); } if (l 0 stock 0) { ans dfs_memo(r, l - 1, stock - 1); } memo[r][l][stock] ans; return ans; } int main() { int m, n; scanf(%d %d, m, n); memset(memo, -1, sizeof(memo)); // 初始化为-1表示未计算 printf(%lld\n, dfs_memo(m, n, 0)); return 0; }这个版本效率高了很多可以处理m, n在20左右的数据。注意stock维度大小是MAX_M1因为stock最大可能是m当所有R都先处理时。4.3 动态规划实现这是我最推荐的方法既高效又简洁。#include stdio.h #include string.h #define MAX 21 // 根据题目数据范围设定 int main() { int m, n; scanf(%d %d, m, n); long long dp[MAX][MAX] {0}; // dp[i][j] 表示使用了i个Rj个L的方案数 dp[0][0] 1; // 边界条件 for (int i 0; i m; i) { for (int j 0; j n; j) { if (i 0 j 0) continue; // 状态转移 if (i 0) { // 最后一个处理的是R从(i-1, j)转移过来总是合法的 dp[i][j] dp[i - 1][j]; } if (j 0 i j) { // 最后一个处理的是L从(i, j-1)转移过来需要满足i j dp[i][j] dp[i][j - 1]; } } } printf(%lld\n, dp[m][n]); return 0; }这个DP的循环顺序很关键。i和j都是从0开始递增这保证了在计算dp[i][j]时dp[i-1][j]和dp[i][j-1]都已经被计算过了。条件i j确保了序列的合法性。这个算法的时间复杂度是O(m*n)空间复杂度O(m*n)可以通过滚动数组优化到O(n)但对于竞赛来说这个空间通常可以接受。4.4 组合数学公式法实现这种方法最直接但需要注意组合数的计算精度和范围。#include stdio.h // 计算组合数 C(a, b)使用 long long适用于较小范围 long long comb(int a, int b) { if (b 0 || b a) return 0; if (b a - b) b a - b; // 利用对称性减少计算量 long long res 1; for (int i 1; i b; i) { res res * (a - i 1) / i; // 逐项计算避免先乘后除的溢出 } return res; } int main() { int m, n; scanf(%d %d, m, n); // 公式f(m, n) C(mn, n) - C(mn, n-1) long long ans comb(m n, n) - comb(m n, n - 1); printf(%lld\n, ans); return 0; }这里comb函数采用递推乘法计算组合数res res * (a - i 1) / i这个顺序很重要先乘后除可以保证每一步除法都是整除因为组合数一定是整数从而避免浮点数误差。但要注意即使这样当a很大时中间结果res * (a - i 1)仍可能溢出long long。所以这种方法只适用于数据范围明确且不大的情况。5. 边界条件与易错点分析那些年我们踩过的坑即使思路正确代码也可能因为边界条件处理不当而功亏一篑。下面总结几个在实现这道题时常见的“坑”。5.1 对m和n大小关系的理解题目描述是“有m个人还鞋n个人借鞋”并没有明确说m n。但从实际意义和约束条件“任何时刻还鞋人数不少于借鞋人数”来看如果m n那么最终必然会出现某个前缀中借鞋人多于还鞋人的情况因为总数上L就比R多。所以合法的前提是m n。在代码中我们应该先判断如果m n直接输出0。这是一个重要的边界条件能避免无谓的计算和可能的错误。5.2 初始状态的合法性在递归或DP中初始状态是什么是(0,0)还是(m, n)这取决于状态定义。在我们的DP定义dp[i][j]已使用i个Rj个L中初始状态dp[0][0] 1表示一个空序列是合法的。这很直观。但在有些人的思路里可能会从第一个位置开始枚举这时第一个位置必须是R否则序列非法。这两种思路是等价的但初始化的方式不同。如果从第一个位置开始枚举相当于默认了dp[1][0] 1。关键是要自洽。5.3 组合数计算的溢出问题这是公式法最容易出错的地方。即使使用long longC(40, 20)的结果已经很大了约1.38e11还在long long范围内。但如果mn更大比如达到60C(60,30)就远超long long的范围了。蓝桥杯的评测数据有时会设计得比较大比如mn17时结果C(34,17) - C(34,16)是2333606220还在int范围内吗int最大约21亿这个数超过了所以必须用long long。如果数据再大比如mn20结果C(40,20)-C(40,19)是6564120420也还在long long范围内long long最大约9e18。但为了保险最好使用unsigned long long或者高精度计算。在竞赛中如果题目没有明确说明用long long通常是安全的但心里要有这根弦。5.4 递归深度与栈溢出纯递归解法不仅时间爆炸递归深度也可能达到mn最大40对于C语言默认的栈空间来说40层递归完全没问题。但如果用Python等语言写深度递归或者数据范围增大就需要考虑栈溢出或设置递归深度限制了。记忆化搜索和DP是更稳妥的选择。5.5 状态转移条件的严格性在二维DP中转移方程是dp[i][j] dp[i-1][j] dp[i][j-1]当i j时。 注意dp[i][j-1]的转移条件为什么是i j而不是i j-1因为i j-1等价于i j。但这里有一个细节当i j时从dp[i][j-1]转移过来是合法的吗dp[i][j-1]的状态是使用了i个R和j-1个L此时库存为i - (j-1) 1。再放一个L库存变为0仍然满足0的条件。所以i j时转移是合法的。如果错误地写成i j就会漏掉ij的情况导致结果偏小。6. 测试与验证如何确保代码的正确性写完代码如何验证它是正确的不能只靠样例。这里提供几个测试思路。6.1 小数据暴力枚举对于m和n很小的情况比如都小于5我们可以写一个简单的暴力程序生成所有可能的排列C(mn, m)种然后逐个检查是否满足前缀条件。将暴力程序的结果与我们优化算法DP或公式的结果对比确保完全一致。这是最可靠的验证方法。6.2 利用已知数列验证卡特兰数有已知的前几项C_01, C_11, C_22, C_35, C_414, C_542, ...。 当mn时我们的结果应该等于C_n。可以测试(1,1) - 1,(2,2) - 2,(3,3) - 5,(4,4) - 14。 对于m ! n的情况也可以找一些特例(m, 0)只有一种排列全部是R。公式C(m,0)-C(m,-1)1-01正确。(m, 1)相当于在m1个位置中选一个位置放L但不能放在第一个位置否则第一个前缀L就比R多。所以有m种放法。公式C(m1,1)-C(m1,0) (m1)-1 m正确。(2,1)我们手动枚举过是2种。公式C(3,1)-C(3,0)3-12正确。6.3 对比不同算法的结果用递归小数据、记忆化搜索、DP、公式法分别实现对同一组输入看输出是否一致。这是交叉验证的好方法。6.4 边界测试测试m0, n0应该是1空序列m0, n0应该是0m0, n0应该是1m n应该是0。确保代码在这些 corner case 下行为正确。7. 性能优化与扩展思考当数据范围变大蓝桥杯的题目有时会逐步加大数据范围来区分不同水平的选手。假设m和n最大可以达到1000甚至10000我们的算法该如何应对7.1 动态规划的空间优化二维DP数组dp[m][n]在mn1000时需要大约1000*1000*8字节 ≈ 8MB可以接受。但如果到10000就需要800MB内存可能不够。我们可以观察到状态转移只依赖于当前行和上一行更准确地说是dp[i-1][j]和dp[i][j-1]因此可以使用滚动数组将空间优化到O(n)。#include stdio.h #include string.h #define MAX_N 10005 int main() { int m, n; scanf(%d %d, m, n); long long dp[MAX_N] {0}; // 一维数组dp[j] 相当于原二维数组的 dp[i][j] dp[0] 1; // 初始化对应 dp[0][0] 1 for (int i 0; i m; i) { // 注意这里需要从右向左更新因为 dp[j] 依赖于 dp[j]上一轮的即dp[i-1][j]和 dp[j-1]本轮已经更新的即dp[i][j-1] // 但我们的转移方程是 dp[i][j] dp[i-1][j] dp[i][j-1]其中 dp[i][j-1] 需要在本轮循环中先于 dp[i][j] 计算。 // 所以我们应该从左向右更新。 // 然而从左向右更新时dp[j] 会被覆盖我们需要一个临时变量保存上一行的值吗 // 其实不需要因为 dp[i-1][j] 就是上一轮循环中的 dp[j]还没被本轮更新覆盖。 // 而 dp[i][j-1] 是本次循环中刚刚计算出来的新值。 // 所以我们可以从左向右更新用 dp[j] 表示 dp[i][j]。 for (int j 0; j n; j) { if (i 0 j 0) continue; long long from_up 0; // 来自上一行 dp[i-1][j] long long from_left 0; // 来自左边 dp[i][j-1] if (i 0) { from_up dp[j]; // 注意在进入j循环时dp[j]还保存着上一轮i-1的值 } if (j 0 i j) { from_left dp[j - 1]; // dp[j-1] 在本轮循环中已经被更新为 dp[i][j-1] } dp[j] from_up from_left; } } printf(%lld\n, dp[n]); return 0; }这个滚动数组版本需要仔细处理更新顺序。更清晰的做法是使用两个数组dp_old和dp_new分别代表上一行和当前行。7.2 公式法与大数运算如果数据范围极大比如m, n上万DP的O(m*n)时间复杂度可能也无法承受上亿次运算。这时公式法O(n)计算组合数的优势就体现出来了。但组合数本身的值会巨大无比远远超出任何基本数据类型的范围。题目可能要求输出结果对一个素数P取模这就引入了数论和模运算。计算C(a, b) mod P有几种方法预处理阶乘和逆元当P是素数且a, b P时可以预处理出1! ~ a! mod P以及每个阶乘的逆元利用费马小定理然后C(a,b) fact[a] * inv_fact[b] % P * inv_fact[a-b] % P。这是最常用的方法。Lucas定理当a, b很大但P不太大时可以用Lucas定理将大组合数分解为若干小组合数的乘积。对于不取模的大整数输出那就需要完整的高精度运算大数乘除法实现起来非常复杂在竞赛中较少见。7.3 问题变种与扩展“未名湖边的烦恼”是一个经典的模型它可以衍生出许多变种问题出栈序列问题一个栈的入栈序列为1,2,...,n求有多少种不同的出栈序列。这就是mn的情况。括号匹配问题求n对括号的合法序列数。找零问题有足够多的1元和2元纸币支付n元有多少种方法不考虑顺序这不太一样但有些神似。路径问题从网格左下角到右上角不穿过对角线的路径数。增加限制如果还鞋和借鞋的人内部也有顺序比如分男女或者有多个窗口问题就变得更复杂了。理解了这个核心模型再遇到这类问题就能迅速识别并套用或修改相应的算法了。8. 从解题到出题思维模式的转变作为一名经历过不少竞赛的“老手”我越来越觉得吃透一道经典题目的最好方式就是尝试自己出几道变式题。对于“未名湖边的烦恼”我们可以从哪些维度去变化创造出新的题目呢8.1 改变约束条件原题约束是“任何前缀中R的数量 L的数量”。我们可以改成“任何前缀中R的数量 L的数量”即严格大于。那么初始状态就不能是stock0而必须是stock1。这相当于路径不能接触对角线yx。答案会变成C(mn, n) - C(mn, n1)如果我没记错的话需要重新推导。“任何前缀中R的数量和L的数量之差不超过k”。这就引入了新的状态维度stock的上限。DP状态需要变成dp[i][j][s]其中0 s k。8.2 改变操作对象原题是两种操作R和L。我们可以增加操作种类有三种人还鞋(R)借冰鞋(L1)借冰刀(L2)。库存有两种物品。约束可能变成冰鞋和冰刀的库存分别不能为负。这就变成了二维库存的DP问题。操作带有权重比如还鞋需要时间t1借鞋需要时间t2求所有合法序列中总时间最短的。这就变成了DP求最优值而不是计数。8.3 改变目标原题是计数。我们可以改成求第k小的合法序列字典序。这需要结合计数和构造用数位DP的思路逐位确定。求一个随机的合法序列。我们可以用递归根据左右子树的方案数比例随机选择走哪边。8.4 结合其他数据结构给出一个序列判断它是否合法。这很简单模拟一遍维护库存stock出现负数即非法。给出一个合法序列求它是所有合法序列中字典序第几大的。这是上面第k大问题的逆问题。通过这样的思维训练不仅能加深对原题的理解更能提升举一反三、灵活运用知识的能力。下次再看到类似“约束”、“前缀”、“计数”的关键词你就能立刻联想到卡特兰数、二维DP、路径计数这些模型解题速度自然就上去了。这道“未名湖边的烦恼”虽然名字起得文艺但内核却是一个扎实的算法基础题。它像一把钥匙打开了组合数学和动态规划的一扇门。从最笨的递归搜索到记忆化再到优雅的DP和简洁的数学公式我们看到了算法优化之美。更重要的是通过它我们掌握了一种将生活问题抽象为数学模型并用计算机思维求解的完整流程。这或许就是算法竞赛带给我们的超越题目本身的乐趣和价值。