“地宫取宝”这道题来自2014年蓝桥杯C/C++省赛真题，是那几年里把“记忆化搜索”和“动态规划”结合得贼妙的一道题。我第一次刷到它的时候，第一反应是：这不就是个带约束的走格子问题吗？结果参照模板改了半天，越改越乱。后来耐着性子把状态设计、递归边界、取模细节全理了一遍，才体会到这题真正考的不是“能不能想到DP”，而是“能不能把约束条件干净地塞进状态里”。
这篇文章我会把这题的完整思路、建模过程、可直接AC的代码、以及我踩过的坑全部拆给你。适合正在备赛的同学、想补DP基础的朋友，也适合刷题时卡在某一步想看一眼别人怎么处理的人。
1. 把题目先完整读明白：地宫取宝到底在做什么
1.1 一个走格子游戏，叠加了两层约束
先还原一下背景。国王的地宫是一个n行m列的网格，每个格子里放了一件宝物，宝物有一个价值。小明从左上角出发，也就是(1,1)，一路向右下走，走到右下角(n,m)，每次只能向右或者向下移动一步。每走到一个格子，他可以选择拿或者不拿那件宝物。规则有两个限制：
- 整体拿的宝物数量不能超过K件，最终到达右下角时，如果手里恰好有K件宝物，才算一种合法方案。
- 拿宝物的时候必须严格递增，也就是后拿的宝物价值必须大于之前拿过的所有宝物中的最大值。
最终问：小明从入口到出口，有多少种不同的“走法 + 拿法”组合？答案取模1000000007。
换句话说，表面上是走迷宫，实际上题目在考你两件事：一是路径方向只有右和下，步数其实固定；二是拿宝物的动作受“数量”和“价值单调性”双重限制。把这两个约束处理好，整道题就解开了。
1.2 数据范围决定了算法方向
n和m的最大值都是50，K的最大值是12。这个数据范围很关键：如果用暴力搜索，把每一条路径都枚举出来，从左上角到右下角需要走n + m - 2步，其中需要选择向下走n - 1次，路径总数是组合数C(n + m - 2, n - 1)。当n = m = 50时，这个数大约是C(98, 49)，数值大到无法枚举。每一步还要决定沿途格子拿不拿，如果都乘进去，搜索分支会直接爆炸。
所以暴力DFS一定是不可行的。
但同时也要看到，K最大才12，说明要记录的“手里宝物数量”这一维度很小。格子上的宝物价值范围呢？题目里通常是从0到12的整数，至少从常见的测试数据来看，价值本身不会很大。这就给了我们一个信号：可以围绕“位置x、位置y、当前拿了几件、当前拿到的最大价值”这四维信息做状态缓存。这四维的组合数量大概是50 × 50 × 13 × 13，约42万个状态，完全装得下。
1.3 为什么这道题适合用记忆化搜索而不是直接循环DP
四维状态DP当然可以用多重循环去写，但写起来很容易在遍历顺序上犯糊涂，尤其是“当前最大价值”这一维，它可能是任意值，循环顺序不像普通坐标DP那么直观。记忆化搜索则完全绕开了这个问题，它不关心遍历顺序，只关心“当前状态能不能算，算没算过”。你只需要把“从当前格子出发到终点，在给定剩余拿取条件时的方案数”定义清楚，然后让递归自己去填表。
对我个人来说，记忆化搜索还有另一个好处：调试的时候可以随时打印某几个状态的返回值，思考过程更接近人类脑补的方式。
2. 从暴力递归到四维状态：建模思路全拆解
2.1 先想清楚每一步到底面临什么选择
假设现在小明站在格子(x, y)，手里已经拿了cnt件宝物，已经拿过的宝物里最大价值是v。那么他面临的无非是两种操作：
- 不拿当前格子的宝物，直接往右或者往下走。
- 拿当前格子的宝物，前提是：宝物价值a[x][y] > v，且cnt < K。拿完之后，手里数量变成cnt + 1，最大价值更新为a[x][y]。
这个“不拿”的分支永远存在，因为题目没有强制你每个格子都必须拿。而“拿”的分支不是无条件存在的，必须先过一遍“严格递增”的判断。
这就是状态转移的核心逻辑。剩下的问题只是：这个递归函数从某个状态出发，到底返回什么值？
2.2 “从当前状态到终点的方案数”这个定义有多重要
我见过很多新手在这里卡住。他们的第一版想法往往是“从起点到当前状态有多少种方案”，然后一路往后推，推到终点再合并。这种思路也不是不能做，但它需要另外维护一个“到达某状态方案数”的表，而且当约束条件出现在“终点判断”上时，很容易写漏。
反过来，把递归函数定义成“在当前格子(x, y)，已经拿了cnt件宝物，最大价值是v，继续走到终点时能构成合法方案的方案数”，问题就变成了典型的“从后往前看”的计数问题。因为向后走和向更新状态都属于同一个逻辑，我们只需要在终点处做一次“当前状态是否合法”的判断，其余的让递归自然展开。
这种“以后效性”定义还有一个好处：起点调用时，cnt = 0，v = 某个比所有宝物价值都小的值（比如-1）。只要跑出dfs(1, 1, 0, -1)，答案直接就是题目要求的结果。
2.3 转移方程怎么写才算滴水不漏
设dp[x][y][cnt][v]表示在格子(x, y)，已拿cnt件，最大价值为v，到终点的合法方案数。那么从状态推导：
- 不拿当前格子：dp[x][y][cnt][v] += dp[x+1][y][cnt][v] + dp[x][y+1][cnt][v]
- 拿当前格子：如果a[x][y] > v且cnt < K，则 dp[x][y][cnt][v] += dp[x+1][y][cnt+1][a[x][y]] + dp[x][y+1][cnt+1][a[x][y]]
特别提醒一个容易忽略的地方：当前格子(x, y)如果是终点，拿与不拿都要在终点统一判断。比如终点格子的宝物在“cnt == K - 1”且“a[x][y] > v”时，是可以拿的，拿完刚好凑满K件；如果cnt == K，那当然不拿，直接就是合法。两种都算一种方案，因为“拿不拿”是选择。
最后把四个方向的“向右/向下”都合并完，结果存回dp[x][y][cnt][v]，下次再遇到相同状态直接返回。这样可以避免重复计算。
3. 记录状态时的两个关键细节
3.1 为什么要把“最大价值”这一维当索引存
你可能已经注意到了，v是“当前手里宝物最大值”，它理论上可以是一个非常随意的整数。但如果v特别大，比如超过12，那么它作为状态索引会占据巨大的空间，这是不可接受的。
回过头看数据范围，宝物价值通常是0到12之间的整数，所以v的取值范围其实很小。哪怕某些用例里有价值超过12的测试数据，题目也会刻意把它限制在一个很小的区间内。原因很简单：如果宝物价值可以到100、1000，那么四维DP的第四维就爆炸了，题目的难度会瞬间从“动态规划入门题”变成“别的什么东西”。所以放心按“价值上限不超过12”来做，这是常识性判断。
3.2 初始最大价值设为-1还是0，差别很大
不少人拿起点上的宝物时就习惯性地让v从0开始。但如果第一件宝物价值是0，而你又把v初始化成0，那么“a[x][y] > v”这个条件会变成“0 > 0”，直接导致第一件价值为0的宝物永远拿不了。这是个非常隐蔽的坑。
解决方式就是让初始v = -1。这样即使格子里的宝物价值是0，也能满足“0 > -1”，第一件宝物就可以正常拿起。相应地，dp数组第四维索引要从“v + 1”开始存，因为数组下标不能是负数。比如把dp[x][y][cnt][v+1]作为缓存位置，v = -1时就存到索引0，v = 0时就存到索引1，v = 12时索引13。
提示：这种“哨兵值”的技巧在很多涉及递增序列的题里都出现过。以后看到“严格递增”条件，第一反应就应该是初始化成一个比最小可能值还小的哨兵。
3.3 边界条件，尤其是终点格子的处理
递归函数最怕两件事：一是越界，二是不知道什么时候返回。这里我建议把越界返回0作为第一道防线。只要有某个方向超出网格，直接返回0，因为它不构成一条合法路径。
终点的处理要格外小心。我见过很常见的错误是把终点先做“上下左右走完后”再判断，结果发现终点格子的宝物根本来不及拿。其实可以这样写：当x == n且y == m时，先检查“cnt == K”是否成立，成立则返回1；再检查“cnt == K - 1且a[x][y] > v”是否成立，成立也返回1；否则返回0。注意这两种情况是互斥的，因为cnt不可能同时等于K和K-1。
如果你非要把终点当成普通格子处理，也不是不行，但那么做需要在撤回递归的时候额外补一次条件判断，反而更繁琐。
4. 代码实现：一份可以直接跑通的记忆化搜索
4.1 完整代码
我直接把能过测试的完整代码贴出来，加上适量的注释：
#include <bits/stdc++.h> using namespace std; const int MOD = 1000000007; int n, m, K; int a[55][55]; long long dp[55][55][15][15]; // dp[x][y][cnt][v+1] long long dfs(int x, int y, int cnt, int v) { // 1. 越界 if (x > n || y > m) return 0; // 2. 记忆化：已经算过这个状态 if (dp[x][y][cnt][v + 1] != -1) { return dp[x][y][cnt][v + 1]; } // 3. 终点特判 if (x == n && y == m) { if (cnt == K) return 1; if (cnt == K - 1 && a[x][y] > v) return 1; return 0; } // 4. 向下、向右搜索 long long ans = 0; // 不拿当前格子的宝物 ans = (ans + dfs(x + 1, y, cnt, v)) % MOD; ans = (ans + dfs(x, y + 1, cnt, v)) % MOD; // 拿当前格子的宝物，需要满足数量与递增条件 if (cnt < K && a[x][y] > v) { ans = (ans + dfs(x + 1, y, cnt + 1, a[x][y])) % MOD; ans = (ans + dfs(x, y + 1, cnt + 1, a[x][y])) % MOD; } // 5. 存进缓存再返回 dp[x][y][cnt][v + 1] = ans; return ans; } int main() { cin >> n >> m >> K; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { cin >> a[i][j]; } } memset(dp, -1, sizeof(dp)); cout << dfs(1, 1, 0, -1) << endl; return 0; }这个版本的核心思路不复杂：每个状态最多算一次，算完就存，遇到相同状态直接取。注意看dfs(1, 1, 0, -1)这个入口，cnt从0开始，v从-1开始，意思是我还没有拿任何宝物，也没有任何价值作为参考。
4.2 为什么答案不会超时
每个格子最多有四个维度的状态组合，总状态数上限大约是50 × 50 × 13 × 13 = 422500。每次状态转移的常数很小，无非是查一下缓存、算几个加法，所以即使全量跑一遍也完全可以接受。相比之下暴力DFS的组合数是指数级的，差距是天上地下。
4.3 为什么dp数组要开成long long并取模
方案数会非常大，一旦n、m都较大，路径数本身就有天文数字级别，更别说每种路径上还要叠加拿与不拿的选择。所以必须在每次累加后立即取模，避免long long溢出。有些选手喜欢最后统一模一次，但中间过程可能早就爆掉了，我建议每次都模，虽然慢一点点，但安全。
5. 常见问题与坑点：我刷这题时踩过的那些雷
5.1 为什么我写循环版DP的时候总是错
循环版DP需要自己确定遍历顺序，尤其是“最大价值”这一维，它不是简单的从左到右、从上到下。如果循环顺序不对，前面的状态没算完就被后面的状态引用，结果自然错得离谱。记忆化搜索就完全没有这个问题，它天然是“用的时候才算”。所以我个人建议这题直接用递归 + 记忆化，别强行循环。
5.2 边界值问题：起点宝物价值为0时拿不了
这题有一个很强的迷惑点：很多用例里起点的宝物价值就是0。如果你把初始最大价值看成0，那么“a[x][y] > v”就是“0 > 0”，起点宝物永远拿不了。即使某些用例起点宝物价值不为0，这种做法也迟早会在某个价值为0的格子翻车。所以一定要用-1作为“还没拿任何宝物”的哨兵值。
5.3 终点边界写错，导致漏掉“终点宝物可拿”的情况
最开始我写终点时只判断了cnt == K，忘了cnt == K - 1时也可以在终点拿最后一件。结果不少用例差1。后来才意识到，终点本质上也是一个普通格子，拿与不拿需要同时讨论清楚。把两种情况都写出来，分别判断，才算完整。
5.4 剪枝：cnt已经大于K时，可以直接返回0
正常状态下cnt不会超过K，但为了防止某些意外路径把cnt累加过头，可以在递归开头加一行“if (cnt > K) return 0”。当然，如果你严格按照“cnt < K”才拿宝物的逻辑，cnt永远不会超过K。不过加上这层保险总归不亏。写代码的时候把“cnt > K”当成防御性检查，能避免非法状态蔓延。
5.5 取模其实可以更激进，但没必要
有人会把取模放在最后一步，认为中间加几次不会溢出。这个判断在n、m很小时成立，但在最大数据下，中间累加的方案数可能远超long long范围。稳妥起见，我选择每一步加法都取模。代价只是几次取模运算，对于这个数据规模来说完全忽略不计。
6. 如果想把代码改成递推版，怎么改才不容易出错
我理解有些同学在做题的时候更习惯递推DP，虽然这题我推荐记忆化搜索，但如果确实想用递推，也可以。关键点是先枚举“最大价值”这一维，让它从小到大递增，再处理常规坐标遍历。大概思路是：从终点往起点方向递推，把dp[x][y][cnt][v]的值通过后面的状态累加起来。不过这样写的时候，v的递增顺序和cnt的递减方向容易绕晕，不如直接记忆化来得稳。
如果你还是想尝试递推，我建议你写完之后，专门跑几个手算的小用例来验证。用小数据对拍，一旦发现结果对不上，就回去检查v的枚举顺序，这比对着空想强得多。
7. 从这道真题里，我总结出的套路化思考方法
这题做完之后，我最大的感受是：它就是把3种基础题型揉到了一起——走格子的路径计数、背包类“拿与不拿”的选择、以及“严格递增序列”的DP维护。蓝桥杯这类竞赛题经常干这种事，表面是一个花哨的背景，内核却都是经典模型。
再往后做题，我遇到类似的题会先问自己三个问题：
- 状态空间里到底哪些信息是“当前决策”所必需的？
- 能不能把所有状态压缩到可枚举的小范围内？
- 边界条件里有没有容易被忽略的“最后一步特殊处理”？
这三个问题思考清楚了，动态规划题的难度会迅速下降。地宫取宝这题就是最好的练手素材，49x49的地图看起来吓人，实际上状态空间小得可怜；约束条件看起来复杂，实际上就是两个if。别被题目唬住，拆开揉碎之后，它不过是一道“记忆化搜索 + 边界处理”的经典题。
最后再送一个我自己的小习惯：这题涉及数组下标与价值之间的偏移映射，我每次提交前都会专门检查“当前最大价值初始值”和“数组索引偏移值”是否配套。只要这个对了，答案基本就稳了一大半。刷题嘛，细节决定AC还是WA。
