[蓝桥杯][2014年第五届真题]地宫取宝

题目

题目链接

题解

记忆化搜索 或 动态规划。

（都不好想）

记忆化搜索。

四维数组。 看代码吧。

觉得像dp又觉得像dfs，最后想写记忆化，但是感觉不大对就没敢写。 虽然应该写不出来，但是确实应该写写试试。 记忆化搜索弱项！

更新于2022.4.2

动态规划。

状态定义：f[i][j][k][v]表示位于(i,j)时，获取到p个物品，最大价值小于v的方案数。

转移方程：

① 不拿(i,j)位置的物品，f[i][j][k][v] += f[i-1][j][k][v] + f[i][j-1][k][v]，比较简单； ② 拿(i,j)位置的物品，只有满足k>=1且v > a[i][j]的时候才能拿，f[i][j][k][v] += f[i-1][j][k-1][a[i][j]] + f[i][j-1][k-1][a[i][j]]。

我看很多人不理解第二个转移方程，还是从定义的状态入手理解。

f[i][j][k][v]表示位于(i,j)时，获取到p个物品，最大价值小于v的方案数。我们当前枚举到的v，对于(i,j)位置的物品，如果它的价值小于v，那么f[i][j][k][v]才能由拿(i,j)物品的状态转移过来。

也就是说f[i][j][k][v]本质上由四个状态转移而来，上面&拿，左面&拿，上面&不拿，左面&不拿，此处的拿与不拿是指拿不拿(i,j)物品。但是并不是在任何情况下，从这四个状态转移到f[i][j][k][v]都是合法的，比如，f[i][j][k][v]是到(i,j)且拿了k个物品最大价值小于v，如果(i,j)价值大于等于v，我拿起它，那么手中的最大价值就是这个物品的价值了，这个价值又比v大，那f[i][j][k][v]怎么可能是由这个状态转移来的。上面是逆推理解，我们正序理解一下，我拿起了(i,j)物品，结果我手中物品的最大价值居然比(i,j)物品的价值还小，这不离谱吗。

我觉得不理解这个，完全是因为没理解什么是动态规划，没理解动态规划是如何递推的。

初始化：(i == 0 || j == 0)：d[i][j][k][c]=0

还有一部分初始化需要在递推中进行：(1,1)位置的物品，我们不拿它是一种方案，拿它也是一种方案（注意还是要满足上面说的条件），这两种情况下都要初始化为1。

代码

记忆化搜索

#include
using namespace std;
const int MOD = 1000000007;

int n, m, k;
int a[55][55], dp[55][55][15][15]; // dp[i][j][p][q]：位于(i, j)时，获取到p个物品，最大价值为q的方案数 

int dfs(int x, int y, int kk, int mm) {
	if(dp[x][y][kk][mm+1] != -1) return dp[x][y][kk][mm+1]; // 已经被更新过了，加一是因为存在价值为0的物品，避免与未拿任何商品的情况相混淆，因此将商品价值对应加一作为dp第四维的索引 
	
	if(x==n && y==m) {
		if(kk == k || (kk == k-1 && a[x][y] > mm)) return dp[x][y][kk][mm+1] = 1; // 到达右下角，若已经拿了k个，无需拿右下角这个；若已经拿了k-1个，且最后一个小于之前难的k-1个中的最大值，则拿上最后一个也满足条件了 
		else return dp[x][y][kk][mm+1] = 0; // 其他情况不属于满足条件的情况，因此方案数返回0 
	}
	
	int res = 0;
	
	if(x+1 m>>k;
	for(int i = 1;i a[i][j];
	
	memset(dp, -1, sizeof dp); // -1表示未更新过 
	
	dfs(1, 1, 0, -1);

	cout n >> m >> K;
	for (int i = 1;i  a[i][j], maxv = max (maxv, a[i][j]);
	maxv ++; // f的定义是“小于v的方案数” 
	
	for (int i = 1;i