解题思路: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分
18 人评分
因为没有类似a[-1]的数组,中括号里只能为正数,但这里初始价值为-1,如果不加一,返回的就是dp[0][0][0][-1],但其实第四个中括号里的值不能为负数,所以加一吧。我自己的理解。
同问,为什么maxv要加1啊
北川 2021-02-25 20:03:56 |
maxv+1是因为价值可以为0,所以价值的初始值要为-1,如果价值规定是大于0的话可以不用+1,直接从dfs(1,1,0,0)开始
你好, 能解释一下为什么maxv要加一吗?我有点不太明白
头发你快长 2020-02-05 16:34:43 |
搜索的起始点是dfs(1,1,0,-1)其中-1的原因就是因为宝物的价值有可能是0,所以即使是零也要进行搜索判断的,所以刚开始置为-1,而这样做又会出现新的问题:数组越界,开辟的数组dp,都知道数组是从0开始数,-1的存在会使数组报错,但是一般c++编译器不会报这个错误,java的会,所以在进行数组操作的时候需要将maxv+1
数组与指针的问题浏览:760 |
蛇行矩阵 (C语言代码)浏览:559 |
川哥的吩咐 (C语言代码)浏览:663 |
母牛的故事 (C语言代码)浏览:625 |
数列问题 (C语言代码)浏览:1068 |
小O的数字 (C语言代码)浏览:1490 |
C语言程序设计教程(第三版)课后习题9.10 (C语言代码)浏览:660 |
C语言程序设计教程(第三版)课后习题3.7 (C语言代码)浏览:620 |
C语言程序设计教程(第三版)课后习题5.5 (Java代码)浏览:563 |
C语言程序设计教程(第三版)课后习题8.2 (C++代码)浏览:671 |