蓝桥杯2014年第五届真题-地宫取宝 （C++代码）记忆化搜索+动态规划

解题思路:

（好难，我看了大量别人写的题解弄出来的）
记忆化搜索+动态规划
参考代码:

#include<bits/stdc++.h>
#define hh ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const int maxn=55;
int n,m,k;
ll mp[maxn][maxn];
ll dp[maxn][maxn][15][15];
//i，j位置,sum（初始为0，此时还没有拿宝贝）,max_（此时没有宝贝，即为-1）
ll dfs(int i,int j,int num,int max_) {
	//判断这个状态是否已经走过
	if(dp[i][j][num][max_+1]!=-1) {
		return dp[i][j][num][max_+1];
	}
	//到达出口
	if(i==n&&j==m) {
		if(num==k||num==k-1&&max_<mp[i][j]) {
			return dp[i][j][num][max_+1]=1;	//满足条件 ,当前1种方案
		} else {
			return dp[i][j][num][max_+1]=0;	//不满足条件 ，当前0种方案
		}
	}
	//可以向下走
	ll s=0;
	if(i+1<=n) {
		if(max_<mp[i][j]) {
			s+=dfs(i+1,j,num+1,mp[i][j]);
		}
		s+=dfs(i+1,j,num,max_);
	}
	//可以向右走
	if(j+1<=m) {
		if(max_<mp[i][j]) {
			s+=dfs(i,j+1,num+1,mp[i][j]);
		}
		s+=dfs(i,j+1,num,max_);
	}

	return dp[i][j][num][max_+1]=s%1000000007;
}
int main() {
	hh;
	memset(mp,0,sizeof(mp));
	memset(dp,-1,sizeof(dp));
	cin>>n>>m>>k;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			cin>>mp[i][j];
		}
	}
	dfs(1,1,0,-1);
	cout<<dp[1][1][0][0]<<endl;
	return 0;
}