地宫取宝---dfs‘记忆

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
int n,m,k;
int vis[52][52];
int dx[2]={0,1};
int dy[2]={1,0};
ll dp[52][52][15][15];///dfs几个变量就几维数组，
///n,m,k,ci的值都较小，所以用dfs
///大了用动归，bfs等 
ll dfs(int x,int y,int c,int ma)
{
	if(x==n&&y==m&&c==k)///满足条件 
	{
	return 1;	
	}
	if(c>k) return 0;								   ///记忆化的优势--剪枝 
	if(dp[x][y][c][ma+1]!=-1) return dp[x][y][c][ma+1];///加1是为了初始值为-1，
													   ///因为有价值为0的		 
	int w=0,e=0;
	for(int i=0;i<2;i++)
	{
		int tx=x+dx[i];
		int ty=y+dy[i];
		if(tx>=1&&tx<=n&&ty>=1&&ty<=m)
		{
			if(vis[tx][ty]>ma)
			{
				if(!i) w=(dfs(tx,ty,c+1,vis[tx][ty])+dfs(tx,ty,c,ma))%1000000007;
				else e=(dfs(tx,ty,c+1,vis[tx][ty])+dfs(tx,ty,c,ma))%1000000007;
			}
			else 
			{
				if(!i)
				w=dfs(tx,ty,c,ma)%1000000007;
				else e=dfs(tx,ty,c,ma)%1000000007;
			}
		}
	}
	dp[x][y][c][ma+1]=(w+e)%1000000007; 
	return dp[x][y][c][ma+1];
}
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
    {
    	for(int j=1;j<=m;j++)
    	{
    		cin>>vis[i][j];
		}
	}
	ll s=0;
	memset(dp,-1,sizeof(dp));
	dfs(1,1,0,-1);
	s+=dp[1][1][0][0]%1000000007; ///第一个没拿 
	memset(dp,-1,sizeof(dp));
	dfs(1,1,1,vis[1][1]); 
	s+=dp[1][1][1][vis[1][1]+1]%1000000007;///第一个拿了
	cout<<s%1000000007;
    return 0;
}