pingfan443

思路1：深搜（思路都放到代码里了）
```cpp
	#include<iostream>
	using namespace std;
	const int maxn=55,mod=1000000007;
	typedef long long ll;
	int map[maxn][maxn];
	int n,m,k;
	int  dfs(int x,int y,int cnt,int max)//当前位置 拥有的宝物数量  宝物数量的最大值 
	{
		if(x==n-1&&y==m-1)//1.可能不算右下角的也正好.2如果右下角的比当前的大，算上这一个如果正好也可以增加路径 
		{
			if(cnt==k||cnt+1==k&&max<map[x][y])return 1;
			else return 0;
		}
		ll ans=0;
		if(y+1<m)//向右走
		{
			if(max<map[x][y])
			ans+=dfs(x,y+1,cnt+1,map[x][y]);//符合拿起它 
			ans+=dfs(x,y+1,cnt,max);//可以不拿 
		 } 
		if(x+1<n)//向下走 
		{
			if(max<map[x][y])
			ans+=dfs(x+1,y,cnt+1,map[x][y]);//同上 
			ans+=dfs(x+1,y,cnt,max);
		}
		return ans%mod;
	}
	int main()
	{
		cin>>n>>m>>k;
		for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
		cin>>map[i][j];
		cout<<dfs(0,0,0,-1)<<endl;//一开始宝物数量0 价值-1（因为有的宝物价值有0）

return 0;
	 } 
```
以上代码只能AC部分数据，结果超限

思路2：记忆化搜索
思路：![](/image_editor_upload/20200218035830_55718.jpg)
```cpp
	 #include<iostream>
	 #include<cstring>
	using namespace std;
	const int maxn=55,mod=1000000007;
	typedef long long ll;
	int map[maxn][maxn];
	int dp[maxn][maxn][15][15]; 
	int n,m,k;
	int  dfs(int x,int y,int cnt,int max)//当前位置 拥有的宝物数量  宝物数量的最大值 
	{
		if(dp[x][y][cnt][max+1]!=-1)//判断这个状态是否已经走过，如果走过就直接用记录的数值计算
		//因为宝物有可能为0所以定义max时用最小值-1 这就导致无法作为下标使用  将所有的+1
		return dp[x][y][cnt][max+1];
		if(x==n-1&&y==m-1)//1.可能不算右下角的也正好.2如果右下角的比当前的大，算上这一个如果正好也可以增加路径 
		{
			if(cnt==k||cnt+1==k&&max<map[x][y])return dp[x][y][cnt][max+1]=1;
			else return dp[x][y][cnt][max+1]=0;
		}
		ll ans=0;
		if(y+1<m)//向右走
		{
			if(max<map[x][y])
			ans+=dfs(x,y+1,cnt+1,map[x][y]);//符合拿起它 
			ans+=dfs(x,y+1,cnt,max);//可以不拿 
		 } 
		if(x+1<n)//向下走 
		{
			if(max<map[x][y])
			ans+=dfs(x+1,y,cnt+1,map[x][y]);//同上 
			ans+=dfs(x+1,y,cnt,max);
		}
		return dp[x][y][cnt][max+1]=ans%mod;
	}
	int main()
	{
		cin>>n>>m>>k;
		for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
		cin>>map[i][j];
		memset(dp,-1,sizeof(dp));
		dfs(0,0,0,-1);//一开始宝物数量0 价值-1（因为有的宝物价值有0） 
		cout<<dp[0][0][0][0]<<endl;//记忆搜索时从后向前搜索的

return 0;
	} 
```
AC
参考题解：[传送门](https://blog.csdn.net/u014665013/article/details/45201479 "传送门")

0.0分

2 人评分

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

pingfan443

TA的其他文章

你可能喜欢

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

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

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

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

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

蓝桥杯2014年第五届真题-地宫取宝-题解(C++代码)

评论区

精彩推荐

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

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

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

输出正反三角形（C语言代码）

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

WU-陶陶摘苹果2 （C++代码）

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

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

用筛法求之N内的素数。（C语言代码）

DNA （C语言描述，蓝桥杯）

pingfan443

TA的其他文章

你可能喜欢

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

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

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

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

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

蓝桥杯2014年第五届真题-地宫取宝-题解(C++代码)

评论区

精彩推荐

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

C语言训练-求1+2!+3!+...+N!的和 （C语言代码）

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

输出正反三角形 （C语言代码）

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

WU-陶陶摘苹果2 （C++代码）

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

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

用筛法求之N内的素数。 （C语言代码）

DNA （C语言描述，蓝桥杯）

　　评论区

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

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

输出正反三角形（C语言代码）

用筛法求之N内的素数。（C语言代码）