解题思路: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],但其实第四个中括号里的值不能为负数,所以加一吧。我自己的理解。
2021-02-21 20:52:22
我觉得maxv加1主要是因为防止dp数组越界,并不会造成错误,因为dp能区别出每个状态不一样然后进行存储。
2020-12-18 11:03:09
同问!!!!!!!!!!!!
2020-09-24 08:59:24
同问,为什么maxv要加1啊
2020-03-17 18:35:34
不懂,为什么没有(1,1)的拿与不拿
2020-02-09 21:28:44
你好, 能解释一下为什么maxv要加一吗?我有点不太明白
2020-01-31 21:12:35
  • «
  • 1
  • »