一个人的巴黎

用户名：uq_36478041918

访问量：14999

签　名：

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

　　自我简介：

TA的其他文章

复制书稿(动态规划 + 贪心)
浏览：440

数的划分(DFS + 回溯 +剪枝【每步详解】)(另附DP算法)
浏览：702

数的划分(动态规划背包问题)
浏览：370

你可能喜欢

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

优质题解

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

　　作者: 一个人的巴黎　　　　发表时间：2022-01-27 16:08:14 浏览：1214　|　评论：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分

9 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

压力怪

那个初始化-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语言代码）

C语言训练-求车速（C语言代码）

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

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

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

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

评论区

精彩推荐

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

淘淘的名单（C语言代码）答案错误？？？

简单的a+b （C语言代码）

大神老白（C语言代码）

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

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

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

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）

Hello, world! （C++代码）

1025题解

一个人的巴黎

TA的其他文章

你可能喜欢

母牛的故事 （C语言代码）

C语言训练-求车速 （C语言代码）

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

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

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

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

评论区

精彩推荐

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

淘淘的名单 （C语言代码）答案错误？？？

简单的a+b （C语言代码）

大神老白 （C语言代码）

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

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

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

【求[X,Y]内被除3余1并且被除5余3的整数的和】 （C语言代码）

Hello, world! （C++代码）

1025题解

母牛的故事（C语言代码）

C语言训练-求车速（C语言代码）

　　评论区

淘淘的名单（C语言代码）答案错误？？？

大神老白（C语言代码）

【求[X,Y]内被除3余1并且被除5余3的整数的和】（C语言代码）