HDU1208Pascal's Travels（记忆化搜索）

题目大意：给你一张图，图上的值表示下一次的步数（必定要走这么多步，不是1..k），问从左上角到右下角有多少条路

解题思路：这题类似于HDU1078http://blog.csdn.net/calculate23/article/details/79095287，也是用dp保存当前到终点的最大值，然后dfs就搜沿一个方向的路径数的最大值，两个方向相加就是改点的最大值。如果你走到一个已经优化过的结点，他的值就可以直接用（记忆化搜索），出来0ms代码，题目的数据会超过int，要用大数保存

AC代码如下：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;

__int64 dp[50][50];
int n,map[50][50];

bool pan(int x,int y)
{
	if(x<0||x>n-1||y<0||y>n-1)
		return false;
	return true;
}
/*数据会超过int，大数保存*/
__int64 dfs(int x,int y)
{
	if(x==n-1 && y==n-1)  //达到目的地返回路径数1，让开始到目的地+1即dp数组存的数+1
	{
		return 1;
	}
	if(!pan(x,y) || !map[x][y])   //越界和遇到这条路径数为0  因为一定是不能到达终点的
		return 0;
	if(dp[x][y])   //记忆化，因为dp必定是保存着坐标（x，y）到终点的最大路径数，直接返回值
		return dp[x][y];
	dp[x][y]+=(dfs(x+map[x][y],y)+dfs(x,y+map[x][y]));  //每次在该位置的dp作更新处理，dfs表示该方向这条路的路径最大值  两个方向相加就是该节点到目的的最大值
	return dp[x][y];
}

int main()
{
	int i,j;
	char s[50];
	while(~scanf("%d",&n) && n!=-1)
	{
		getchar();
		for(i=0;i<n;i++)
		{
			scanf("%s",s);
			for(j=0;j<n;j++)
				map[i][j]=s[j]-'0';
		}
		memset(dp,0,sizeof(dp));
		printf("%I64d\n",dfs(0,0));
	}
	return 0;
}