原题链接：蓝桥杯2014年第五届真题-地宫取宝
解题思路: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; }0.0分
16 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复