蓝桥杯2014年第五届真题-地宫取宝 （C++代码） 记忆化搜索！ 利用 dfs+dp！ 巧妙结合！

解题思路:1.明显看出是一个dfs的题，暴力搜索各种路径 2.注意如果只用dfs会超时 3.所以要记忆走过的路径，二者集合起来即为  记忆化搜索！
注意事项:1.这题不仅要搜索，搜索中还得判断是否要拿走宝物，所以是个带参判断的搜索，宝物的价值即为需要考虑的参数。 2.记得用memset()来初始化数组为-1  3.由于宝物可能为0，max初始为-1，dp中要max+1
参考代码:

#include<iostream>
#define N 1000000007 
#include<cstring>
using namespace std;
int n,m,k;
int mapvalue[51][51];
int dp[55][55][15][15];//动态规划路径 
int dfs(int x,int y,int num,int maxv){
     //判断路径有没走过 
if(dp[x][y][num][maxv+1]!=-1)
   return dp[x][y][num][maxv+1]; //走过就用统计过的路径(“记忆”的部分) 
if(x==n&&y==m){  //走到了右下角
     //分拿走或者不拿走右下角那个宝藏,都是一种方案 
   if(num==k||(num==k-1&&maxv<mapvalue[x][y]))
   return dp[x][y][num][maxv+1]=1;
   else return dp[x][y][num][maxv+1]=0;// 否则失败
}
//统计路径方案 
long long s=0;
//向下深搜，分取或者不取这个宝物，由宝物价值判断 
if(x+1<=n){   //向下控制不出界限 
      if(maxv<mapvalue[x][y])
s+=dfs(x+1,y,num+1,mapvalue[x][y]);
s+=dfs(x+1,y,num,maxv);//也可以不取 
}
//向右深搜 分取或者不取这个宝物，由宝物价值判断
if(y+1<=m){ //向下控制不出界 
if(maxv<mapvalue[x][y])
s+=dfs(x,y+1,num+1,mapvalue[x][y]);
s+=dfs(x,y+1,num,maxv);//也可以不取 
  }
   return dp[x][y][num][maxv+1]=s%N;
}
int main(){
int i,j;
cin>>n>>m>>k;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++){
  cin>>mapvalue[i][j];
}
memset(dp,-1,sizeof(dp)); 
    dfs(1,1,0,-1);
    cout<<dp[1][1][0][0];
return 0; }