X国王有一个地宫宝库，是n×m个格子的矩阵，每个格子放一件宝贝，每个宝贝贴着价值标签。地宫的入口在左上角，出口在右下角。小明被带到地宫的入口，国王要求他只能向右或向下行走。走过某个格子时，如果那个格子中的宝贝价值比小明手中任意宝贝价值都大，小明就可以拿起它（当然，也可以不拿

Problem:AcWing1212.地宫取宝文章目录思路解题方法复杂度Code思路这是一个动态规划问题，我们需要找到所有可能的路径，其中每个路径中的宝物价值都是递增的，并且恰好有k个宝物。我们可以使用一个四维的动态规划数组dp[i][j][p][q]，其中i和j表示当前的位置，p表示当前

这是一个dp题，可以用4维数据来表示所有的状态。但是有一个需要注意的点，一般来说，对于每个坐标，有拿跟不拿两种情况，如果没有拿任务宝物的状态表示为0，那么拿取了价值为0的宝物时，要以另一种情况来跟没拿区分。处理的方法就是将所有宝物的价格+1。longlongdp[55][55][15][15];const

一、题目描述[蓝桥杯2014省AB]地宫取宝二、问题简析一开始，我采用\(bfs\)进行搜索，出现了超出内存限制的问题。所以，要进行记忆化搜索，重新采用\(dfs\)。2.1暴力搜索令\(dfs(i,j,cnt,val)=\)从\((i,j)\)开始，有几种路线拿到\(k\)件物品（此时已经取了\(cnt\)件