本文主要是介绍百度之星第四题（记忆化搜索），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
本日志是本人原创，可以转载，但请注明出处，谢谢......Labyrinth
Time Limit: 2000/1000 MS (Java/Others) Memory Limit:32768/32768 K (Java/Others)
Total Submission(s): 519 Accepted Submission(s): 174
Problem Description
度度熊是一只喜欢探险的熊，一次偶然落进了一个m*n矩阵的迷宫，该迷宫只能从矩阵左上角第一个方格开始走，只有走到右上角的第一个格子才算走出迷宫，每一次只能走一格，且只能向上向下向右走以前没有走过的格子，每一个格子中都有一些金币（或正或负，有可能遇到强盗拦路抢劫，度度熊身上金币可以为负，需要给强盗写欠条），度度熊刚开始时身上金币数为0，问度度熊走出迷宫时候身上最多有多少金币？
Input
输入的第一行是一个整数T（T< 200），表示共有T组数据。
每组数据的第一行输入两个正整数m，n（m<=100，n<=100）。接下来的m行，每行n个整数，分别代表相应格子中能得到金币的数量，每个整数都大于等于-100且小于等于100。
Output
对于每组数据，首先需要输出单独一行”Case #?:”，其中问号处应填入当前的数据组数，组数从1开始计算。
每组测试数据输出一行，输出一个整数，代表根据最优的打法，你走到右上角时可以获得的最大金币数目。
Sample Input
2
3 4
1 -1 1 0
2 -2 4 2
3 5 1 -90
2 2
1 1
1 1
Sample Output
Case #1:
18
Case #2:
4
代码解析：
（1）DFS深度优先的方法
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define LL __int64
bool p[100][100]; //访问标记数组
int dx[3]={-1,1,0}; //DFS准备数组（表示x下标位移的移动量）
int dy[3]={0,0,1}; // DFS准备数组（表示y下标位移的移动量）
int value[110][110]; //存储每个方格的黄金数量
int maxx; //表示最大结果
int ans; //临时存放计算DFS的每组结果
int m,n; //m行n列
int max(int x,int y){return x>y?x:y;} //最大值函数
//深度优先遍历
void dfs(int x,int y)
{
p[x][y]=true; //标记为已访问
int i;
ans+=value[x][y];
if(x==0&&y==n-1) //DFS出口，表示遍历到右上角
{maxx=max(maxx,ans);ans-=value[x][y];return;} //返回，并恢复现场（包括ans的恢复）
for(i=0;i<3;i++)
{
if(x+dx[i]<m&&y+dy[i]<n&&x+dx[i]>=0&&!p[x+dx[i]][y+dy[i]]) //不能越界，且未被访问
{
dfs(x+dx[i],y+dy[i]); //分别对该方格的上、下、右进行递归遍历
p[x+dx[i]][y+dy[i]]=false; //遍历结束恢复现场（对p的恢复）
}
}
ans-=value[x][y]; //恢复现场（对ans的恢复）
}
int main()
{
//freopen("in.txt","r",stdin);
int i,j,T;
int count;
while(scanf("%d",&T)!=EOF)
{
count=0;
while(T--)
{
scanf("%d%d",&m,&n);
ans=0;
maxx=-1000050; //最大值初始化为最小可能值
memset(value,0,sizeof(value));
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&value[i][j]);
value[i][n]+=value[i][j];
}
}
memset(p,0,sizeof(p));
dfs(0,0);
printf("Case#%d:\n",++count);
printf("%d\n",maxx);
}
}
return 0;
}
这是最容易想的的方法，然而对于n<=100来说，DFS深度很大会造成超时（Timelimited error）
所以这道题显然不能用DFS解决。
（2）DP动态规划求解
由于题目中说只能向上下和右行进，故如果我们能枚举所有向右行进的时机那么此问题便迎刃而解。
假设：
·dp[i][j]表示从第i-1列适宜位置开始，移动至第i-1列的第j行时向右行进到第i列之前，ans所能积累的最大值。
·d[j][i][k]表示从第i列的第k行移动到第i列的第j行时所积累的和。
那么易知，dp[0][n]即是所求
而dp[0][n]=dp[i][n]+d[0][n][i];
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std ;
const int INF=0xfffffff ; //这是int型最大值
int m,n; //m行n列
int value[105][105],dp[105][105],d[105][105][105];
int max(int x,int y){return x>y?x:y;} //求最大值
int main()
{
int T,i,j,k;
while(scanf("%d",&T)!=EOF)
{
int count=0;
while(T--)
{
for(i=0;i<105 ;i++)
for(j=0;j<105 ;j++)
dp[i][j]=-INF; //初始化记忆搜索数组为int最小值
scanf("%d%d",&m,&n);
for(i=0;i<m ;i++)
for(j=0;j<n ;j++)
scanf("%d",&value[i][j]);
if(n==1) //如果只有一列，直接输出
{
printf("Case#%d:\n%d\n",++count,value[0][0]);
continue ;
}
//对d数组的初始化
memset(d,0,sizeof(d)) ;
for(i=0;i<n ;i++)
{
for(j=0 ;j<m ;j++)
{
for(k=0;k<=j ;k++)
{
if(j==k)
d[j][i][k]=value[j][i];
else
{
d[j][i][k]=d[j-1][i][k]+value[j][i] ;
d[k][i][j]=d[j][i][k];
}
}
}
}
//开始动态规划记忆搜索
dp[0][1]=value[0][0];
for(i=1;i<m ;i++)
dp[i][1]=dp[i-1][1]+value[i][0];
for(i=2;i<n ;i++)
{
for(j=0;j<m ;j++)
{
for(k=0;k<m ;k++)
{
dp[j][i]=max(dp[j][i],dp[k][i-1]+d[k][i-1][j]);
}
}
}
intans=-INF;
for(i=0;i<m ;i++)
{
inttemp=dp[i][n-1]+d[0][n-1][i] ;
ans=max(ans,temp);
}
printf("Case#%d:\n%d\n",++count,ans) ;
}
}
return 0 ;
}
这样解决完毕时间复杂度是O(n^3),而n最大是100,所以这样做不会超时。
这篇关于百度之星第四题（记忆化搜索）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
