蓝桥杯——地宫取宝（记忆化搜索）

题目：

地宫取宝

问题描述：

我们的目标是统计到达终点时身上宝物数量恰为k的方法数：
1、人物初始位于左上角，终点位于右下角；
2、人物仅可以选择向右或者是向下移动；
3、每到达一个格子，若该处的宝物价值高于已携带宝物中的最大价值，则可以选择拿取该宝物收入背包。

---

原因分析

思路一、暴力搜索

题目本身的数据量不算大，直接通过暴力搜索也可以做，也可以通过一部分数据。
但在过程中还是要注意数据范围大小，题目要求对结果取模，这个模也可以说明数据的范围是远大于int的数据范围的，所以还是要使用long long 类型。

#include<bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
#define ll long long
ll cnt;
int a[55][55];
int n,m,k;
void dfs(int x,int y,int maxn,int t){
	if(t>k)return;
	if(y>m||x>n)return;
	if(x==n&&y==m){
		if(t==k||t==k-1&&a[x][y]>maxn){
			cnt++;
			cnt%=mod;
			return;
		}
		return;
	}
	if(a[x][y]>maxn){
		dfs(x+1,y,a[x][y],t+1);
		dfs(x,y+1,a[x][y],t+1);
	}
	dfs(x,y+1,maxn,t);
	dfs(x+1,y,maxn,t);
}
int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	dfs(1,1,-1,0);
	cout<<(cnt%mod);
}

---

思路二、记忆化搜索

题目的数据量不算大，采用暴力搜索超时的情况下，我们可以选择使用记忆化搜索，拿空间来换时间。
之前使用暴力搜索，最大的问题就是需要多次访问一个数据，重复调用导致结果超时，所以我们需要开一个新的数组来储存那些过程中的数据。
在之前的暴力搜索中，有四个元素，所以现在我们需要开一个四维数组，包含了位置的x、y、此时携带物品中的最大价值maxn和已携带宝物数量t（不包括当前位置）。
在我们接下来的过程中，需要重复调用一个数据时，就可以直接调用之前的结果，而不必重复过程。

注意： 宝物的价值可以为0，那么对于第一个位置，我们就需要考虑此时背包所携带物品的最大价值。
如果直接令其为0，那么如果初始位置的宝物价值恰为0，此时我们就相当于直接把它给舍弃了，显然这是有疏漏的；

如果我们令初始的maxn为负数的话，就需要解决另一个问题：数组下标不存在负数。我们的解决办法是将所有的maxn等价为maxn+1，从而避免了下标为0的情况。

#include<bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
int a[55][55];
#define ll long long 
ll dp[55][55][15][15];
ll n,m,k;
ll dfs(int x,int y,int maxn,int t){
	 if(dp[x][y][maxn+1][t]!=-1) return dp[x][y][maxn+1][t];
	ll ans=0;
	if(t>k||y>m||x>n)return 0;
	if(x==n&&y==m){
		if(t==k||(t==k-1&&a[x][y]>maxn)) {
	 		return 1;
	 	}
		return 0;
	}
	if(a[x][y]>maxn){
		ans+=dfs(x+1,y,a[x][y],t+1);
		ans+=dfs(x,y+1,a[x][y],t+1);
	}
	ans+=dfs(x,y+1,maxn,t);
	ans+=dfs(x+1,y,maxn,t);
	ans%=mod;
	dp[x][y][maxn+1][t]=ans;
	return ans;
}
int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
		}
	}
	memset(dp,-1,sizeof(dp));
	cout<<(dfs(1,1,-1,0)%mod);
}

当然了，最简单的办法其实就是对一开始的数据进行加1操作，根本就不会有为0的情况

#include<bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
int a[55][55];
#define ll long long 
ll dp[55][55][15][15];
ll n,m,k;
ll dfs(int x,int y,int maxn,int t){
	 if(dp[x][y][maxn][t]!=-1) return dp[x][y][maxn][t];
	ll ans=0;
	if(t>k||y>m||x>n)return 0;
	if(x==n&&y==m){
		if(t==k||(t==k-1&&a[x][y]>maxn)) {
	 		return 1;
	 	}
		return 0;
	}
	if(a[x][y]>maxn){
		ans+=dfs(x+1,y,a[x][y],t+1);
		ans+=dfs(x,y+1,a[x][y],t+1);
	}
	ans+=dfs(x,y+1,maxn,t);
	ans+=dfs(x+1,y,maxn,t);
	ans%=mod;
	dp[x][y][maxn][t]=ans;
	return ans;
}
int main(){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			a[i][j]+=1;//对结果没有影响
		}
	}
	memset(dp,-1,sizeof(dp));
	cout<<(dfs(1,1,0,0)%mod);
}