地宫取宝 （C++代码）(记忆化搜索)

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int g[100][100];
int d[100][100][50][50];
int n,m,k;
int dp(int x,int y,int num,int big){
	if(d[x][y][num][big]!=-1) return d[x][y][num][big];
	d[x][y][num][big]=0;
	if(x==n&&y==m&&k==num) d[x][y][num][big]=1;
	if(g[x][y]>big&&k>num)
	{
		d[x][y][num][big]+=dp(x,y,num+1,g[x][y]);
		d[x][y][num][big]%=1000000007;
	}
	if(x<n)
	{
		d[x][y][num][big]+=dp(x+1,y,num,big);
		d[x][y][num][big]%=1000000007;
	} 
	if(y<m)
	{
		d[x][y][num][big]+=dp(x,y+1,num,big);
		d[x][y][num][big]%=1000000007;
	}
	return d[x][y][num][big];
}
int main(void){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++){
		cin>>g[i][j];
		g[i][j]++;
	}	
	memset(d,-1,sizeof(d));
	dp(1,1,0,0);
	cout<<d[1][1][0][0]<<endl;
	return 0;
}

使用了记忆化搜索的方式，但是一开始出现了超时的问题，出现超时间限制的情况如下代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int g[100][100];
int d[100][100][50][50];
int n,m,k;
int dp(int x,int y,int num,int big){
	if(d[x][y][num][big]) return d[x][y][num][big];
	d[x][y][num][big]=0;
	if(x==n&&y==m&&k==num) d[x][y][num][big]=1;
	if(g[x][y]>big&&k>num)
	{
		d[x][y][num][big]+=dp(x,y,num+1,g[x][y]);
		d[x][y][num][big]%=1000000007;
	}
	if(x<n)
	{
		d[x][y][num][big]+=dp(x+1,y,num,big);
		d[x][y][num][big]%=1000000007;
	} 
	if(y<m)
	{
		d[x][y][num][big]+=dp(x,y+1,num,big);
		d[x][y][num][big]%=1000000007;
	}
	return d[x][y][num][big];
}
int main(void){
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++){
		cin>>g[i][j];
		g[i][j]++;
	}	
	dp(1,1,0,0);
	cout<<d[1][1][0][0]<<endl;
	return 0;
}

原因是没有使用好记忆化搜索的优势，导致了方法的退化，出现了重复计算的现象

最好的解决方式是

使用一个数组来进行保存是否进行了访问，防止了出错，采用了用空间开换时间的策略

vis[][][][]

没有给出具体的代码，自己实现