地宮取寶（記憶化深搜）

傳送門
題目描述
X 國王有一個地宮寶庫。是 n x m 個格子的矩陣。每個格子放一件寶貝。每個寶貝貼著價值標簽。
地宮的入口在左上角，出口在右下角。
小明被帶到地宮的入口，國王要求他只能向右或向下行走。
走過某個格子時，如果那個格子中的寶貝價值比小明手中任意寶貝價值都大，小明就可以拿起它（當然，也可以不拿）。
當小明走到出口時，如果他手中的寶貝恰好是k件，則這些寶貝就可以送給小明。
輸入格式
輸入一行3個整數，用空格分開：n m k (1<=n,m<=50, 1<=k<=12)
接下來有 n 行數據，每行有 m 個整數 Ci (0<=Ci<=12)代錶這個格子上的寶物的價值

輸出格式
要求輸出一個整數，錶示正好取k個寶貝的行動方案數。該數字可能很大，輸出它對 1000000007 取模的結果。
輸入樣例
2 2 2
1 2
2 1
輸出樣例
2

分析：對 1000000007 取模說明數據量很大，使用long long類型和記憶化深搜；
1、所有寶貝價值加1：因為初始價值可能為0，maxn不能也同時為0 函數裏比較的時候改為>=就不對了（要求撿到的寶貝比之前的都貴才可以）maxn為-1也不行 數組不能是負數，所以要同時加1 這樣最小的初始值為1 互不影響
2、每次ans初始化為0，走到某一步了，後面的每一步都對應的幾種情况，所以dp代錶走到這一步了，可以對應多少種情况，這樣逐漸累加，都return後第一步起點的ans就是總的情况

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1000000007;
ll a[55][55];
ll dp[55][55][15][15];
ll n,m,k;
ll dfs( ll x,ll y,ll maxn,ll t)
{
    
	ll ans=0;
	if(t>k||x>n||y>m) return 0;
	if(dp[x][y][maxn][t]!=-1)
	return dp[x][y][maxn][t];
	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+1,y,maxn,t);
	ans+=dfs(x,y+1,maxn,t);
//遇到合適的寶貝有撿的情况，也有可以不撿起的情况，所以都要遍曆一遍不撿的情况 
	ans%=mod;
	dp[x][y][maxn][t]=ans;
	return ans;
}
int main()
{
    
	scanf("%lld%lld%lld",&n,&m,&k);
	for(int i=1;i<=n;i++)
	for(int j=1;j<=m;j++)
	{
    
		scanf("%lld",&a[i][j]);
		a[i][j]+=1; 
	}
	memset(dp,-1,sizeof(dp));
	printf("%lld\n",dfs(1,1,0,0)%mod);
}