dp与dfs 蓝桥杯2014年第五届真题-地宫取宝

解题思路:

注意事项:

参考代码:

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MOD = 1000000007;

int M[55][55];

int dp[55][55][15][15];

int n,m,k;

//int sx,sy;

//int ex,ey;

int dir[2][2]={{0,1},{1,0}};//右、下 

int dfs(int x,int y,int num,int value){

if(dp[x][y][num][value+1]!=-1){//证明之前已经求过了

return dp[x][y][num][value+1];

} 

int count = 0;

if(x == n&&y==m){

if(num == 0||(num == 1 && M[x][y]>value)){//到达最后一步

//步数num为0，就返回1；

//如果num为1且如果物品价值大于可取价值,证明可以取这最后一个宝物，刚好使num为0，故也返回1 

return 1;

}

} 

// cout<<"x:"<<x<<"y:"<<y<<"count:"<<count<<endl;

for(int i = 0;i < 2;i++){

int dx = x + dir[i][0];

int dy = y + dir[i][1];

if(dx > n||dy > m){//超出地图范围了 

continue;

}

if(M[x][y] > value){

count += dfs(dx,dy,num-1,M[x][y]);//取了当前的宝物 

}

count %= MOD;

count += dfs(dx,dy,num,value);//没有取当前的宝物

count %= MOD;

}

return dp[x][y][num][value+1] = count;//因为value值初始是负数，故需要加个一保证是>=0的数 

}

int main(){

cin>>n>>m>>k;

for(int i = 1;i <= n;i++){

for(int j = 1;j <= m;j++){

cin>>M[i][j];

}

}

memset(dp,-1,sizeof(dp));

cout<<dfs(1,1,k,-1)<<endl;//value设置为-1，避免读不到物品价值为0的情况 

return 0;

}