两种代码便于理解学习 普通DFS/DFS+记忆化搜索

注意：下面有两种代码，第二种是大部分人可以想到的，但是会超时，第一种就是记忆化搜索，

            放两种代码的目的就是说明普通DFS和记忆化+DFS差的不多，便于大家参考学习。

参考代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int n,m,k;
int a[51][51];
LL jy[51][51][13][13];
	//记忆化搜索 每个下标的含义与dfs函数一样 
LL dfs(int x,int y,int num,int max){
	//不等于-1就说明判断过这种情况，可以直接返回存过的值 
	if(jy[x][y][num][max+1]!=-1) return jy[x][y][num][max+1];
	int lmax=a[x][y];
	LL sum=0;
	if(x>n || y>m || num>k) return 0;
	if(x==n && y==m && (k==num || (num==k-1 && lmax>max)))
		return 1;
	if(lmax>max){  //拿宝物 
		sum+=dfs(x+1,y,num+1,lmax);
		sum+=dfs(x,y+1,num+1,lmax);
	}
	//不拿宝物 
	sum+=dfs(x+1,y,num,max);
	sum+=dfs(x,y+1,num,max);
	jy[x][y][num][max+1]=sum;  
	//将这种情况存下来，加1是因为初始是-1，会越界，所以默认所有情况都加1 
	return sum%1000000007;
	
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	memset(jy,-1,sizeof(jy));
	cin >> n >> m >> k;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin >> a[i][j];
	cout << dfs(1,1,0,-1);
	return 0;
}

/*
int a[51][51];
LL sum=0;
int n,m,num;
void DFS(int x,int y,int k,int max){
	int lmax=a[x][y];
	if(x==n && y==m && (k==num || (k==num-1 && lmax>max))){
		sum++;
		sum=sum%1000000007;
		return;
	}
	if(x>n || y>m || k>num)
		return;
	if(lmax>max){  //拿宝物 
		DFS(x+1,y,k+1,lmax);
		DFS(x,y+1,k+1,lmax);
	}
	//不拿宝物 
	DFS(x+1,y,k,max);
	DFS(x,y+1,k,max);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> num;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin >> a[i][j];
	DFS(1,1,0,-1);
	cout << sum;
	return 0;
}
*/