一个人的巴黎

用户名：uq_36478041918

访问量：13210

签　名：

等　　级
排　　名	103
经　　验	8047
参赛次数	1
文章发表	70
年　　龄	0
在职情况	学生
学　　校	NTU
专　　业	计算机科学与技术

　　自我简介：

TA的其他文章

矩阵的幂【写个快速幂矩阵】
浏览：160

蓝桥杯2017年第八届真题-日期问题
浏览：159

蓝桥杯2017年第八届真题-k倍区间【前缀和+数学优化】
浏览：205

你可能喜欢

C语言程序设计教程（第三版）课后习题6.10 （C++代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

优质题解

地宫取宝(DFS+动态规划：记忆化递归)

　　作者: 一个人的巴黎　　　　发表时间：2022-01-27 16:08:14 浏览：1151　|　评论：4　

原题链接：蓝桥杯2014年第五届真题-地宫取宝

以前都是用vis[ ][ ]数组判断该位置有没有被访问过，现在情况有所改动，除了位置，他还带着 “当前手中宝物价值的最大值：max” 以及 “当前手中宝物数：cnt”，所以开辟一个缓存数组cache[x][y][max][cnt]将四种状态都记录

|   |( x ,  y )|(x , y+1)|
| :------------: | :------------: | :------------: |
|   |**(x+1 , y)**|p|
比如说：（x,y)想要到达p点，是向右还是向左，是拾起(x,y)格子处的宝物还是不拾起，无论是怎么到达p点的，如果在p点发现dfs(i,j,max,cnt)中i,j,max,cnt，和缓存中的一样，那就是重复搜索了。可以采用动态规划(dp):动归数组、逐步生成或者记忆性递归，这里采用记忆性递归，因此开辟一个缓存数组。

```cpp
#include<iostream>
#include<algorithm>
#include<cstring>
#define MOD 1000000007
using namespace std;
int n, m, k;
int maze[50][50];
long long ans;
long long cache[50][50][14][13];//缓存数组

long long dfs(int x, int y, int max, int cnt)//不再是void，而是返回long long 类型的方案数ans
{
	//先查缓存，缓存里有，直接用
	if (cache[x][y][max+1][cnt] != -1)//记忆化搜索，
	此处为什么max+1，因为题目中宝物价值是：Ci  (0< =Ci< =12)，包含0，所以可能取到0，那我在main函数调用时初始化max只能是负数，否则如果起始点为0，我就不能拾起了，但数组下标又不能是负数，干脆直接化为max+1，max+1>=0说明拾起第一件宝物
		return cache[x][y][max+1][cnt];
	//如果越界或者当前手中宝物数大于k，退出
	if (x == n || y == m || cnt > k)
		return 0;
	int cur = maze[x][y];//当前宝物价值
	long long ans = 0;
	//走到最后一格
	if (x == n - 1 && y == m - 1)
	{
	    //手中宝物数等于k 或者 手中宝物数比k少1，并且当前格子宝物价值大于手中宝物价值的最大值，可以捡起最后一个宝物，同样符合条件。因此方案数+1
		if (cnt == k||(cnt==k-1&&cur>max))
		{
			ans++;
			if (ans > MOD)//取模操作
				ans = ans % MOD;
		}
		return ans;//返回方案数
	}
	//当前格子宝物价值大于手中宝物价值的最大值，并且拾起该宝物，将方案数叠加
	if (cur > max)
	{
		ans += dfs(x, y + 1, cur, cnt + 1);//向右
		ans += dfs(x + 1,y , cur, cnt + 1);//向下
	}
	//1. 当前当前格子宝物价值大于手中宝物价值的最大值，但不拾起
	//2. 当前当前格子宝物价值小于手中宝物价值的最大值
	ans += dfs(x, y + 1, max, cnt);//向右
	ans += dfs(x + 1, y, max, cnt);//向下
	//写入缓存
	cache[x][y][max+1][cnt] = ans % MOD;
	return cache[x][y][max+1][cnt];//返回方案数
}
int main()
{
	cin >> n >> m >> k;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> maze[i][j];
	memset(cache, -1, sizeof(cache));//初始化为-1
	cout<<dfs(0, 0, -1, 0)<<endl;
	return 0;
}
```

0.0分

8 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

代码纠错

SQL生成与解释

　　评论区

压力怪

那个初始化-1.为啥一定得把dp数组初始化为-1

2022-12-22 21:29:58

hzyyyyyy

有注释就很棒

2022-06-12 11:50:11

哦嘞嘞

棒棒

2022-03-16 23:35:35

一个努力成长的程序媛

大黄好厉害呀！！

2022-02-18 17:20:58

一个人的巴黎

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C++代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

剪刀石头布（C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

地宫取宝(DFS+动态规划：记忆化递归)

评论区

精彩推荐

A+B for Input-Output Practice （C语言代码）

矩阵乘方（C语言代码）

字符串比较（C语言代码）

淘淘的名单（C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言训练-百钱百鸡问题（C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

【亲和数】（C语言代码）

数字统计（C语言代码）

神奇的fans （C语言代码）

一个人的巴黎

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C++代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

剪刀石头布 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

地宫取宝(DFS+动态规划：记忆化递归)

评论区

精彩推荐

A+B for Input-Output Practice （C语言代码）

矩阵乘方 （C语言代码）

字符串比较 （C语言代码）

淘淘的名单 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

C语言训练-百钱百鸡问题 （C语言代码）

C语言程序设计教程（第三版）课后习题7.2 （C语言代码）

【亲和数】 （C语言代码）

数字统计 （C语言代码）

神奇的fans （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

剪刀石头布（C语言代码）

　　评论区

矩阵乘方（C语言代码）

字符串比较（C语言代码）

淘淘的名单（C语言代码）

C语言训练-百钱百鸡问题（C语言代码）

【亲和数】（C语言代码）

数字统计（C语言代码）