POJ1088,二维动态规划

思路：这是我做的第二道二维数组的动态规划，所以很清楚的知道二维的动态规划递归方程是用dp[][]而不是dp[]，所为很容易得到递归公式：dp[i][j]=max(dp[i-1][j],dp[i+1][j],dp[i][j-1],dp[i][j+1]).(在满足条件的情况下),那么我们用个递归函数，里面分别判断(i-1,j)(i+1,j)(i,j-1)(i,j+1)等四个方向是否满足条件（不越界，并且值小于位置(i,j)上的值）.然后在主函数中依次遍历每个点，每个点调用递归函数得到以这个点为起点可以得到的最大路径，然后我们从每个点的最大路径中再选最大的一个，其值+1即为answer。

但是这样会有个问题，那就是会超时，那我们怎样缩短时间呢？我们知道动态规划的思想是以空间换时间，利用其它子问题已经求出的结果，那么看我们这道题，一个点走过一遍就可以得到它的最大路径，那么对于走过的点我们是可以不用再走而直接利用答案的，所以我们用个标记数组，记录走过的点就OK了。

代码如下：

#include<iostream>
using namespace std;
#define len 110
int m,n;
int dp[len][len];
int vis[len][len];
int judge(int i,int j)
{
	if(i>=0&&i<m&&j>=0&&j<n)
		return 1;
	return 0;
}

int setdp(int a[len][len],int i,int j)
{
	if (vis[i][j]==1)
	{
		return dp[i][j];
	}
	vis[i][j]=1;
	int t;
	if(judge(i-1,j)&&a[i][j]>a[i-1][j])
	{
		
		t=setdp(a,i-1,j)+1;
		if(dp[i][j]<t)
			dp[i][j]=t;
	}
	if(judge(i+1,j)&&a[i][j]>a[i+1][j])
	{

		t=setdp(a,i+1,j)+1;
		if(dp[i][j]<t)
			dp[i][j]=t;
	}
	if(judge(i,j-1)&&a[i][j]>a[i][j-1])
	{

		t=setdp(a,i,j-1)+1;
		if(dp[i][j]<t)
			dp[i][j]=t;
	}
	if(judge(i,j+1)&&a[i][j]>a[i][j+1])
	{

		t=setdp(a,i,j+1)+1;
		if(dp[i][j]<t)
			dp[i][j]=t;
	}	
	return dp[i][j];
	
}
int main()
{
	scanf("%d",&m);
	scanf("%d",&n);
	int a[len][len];
	int i,j;
	int max;
	memset(dp,0,sizeof(dp));
	memset(vis,0,sizeof(vis));
	for(i=0;i<m;i++)
		for(j=0;j<n;j++)
		{
			scanf("%d",&a[i][j]);
		}
	for(i=0;i<m;i++)
		for(j=0;j<n;j++)
		{
			setdp(a,i,j);
		}
	max=0;
	for(i=0;i<m;i++)
		for(j=0;j<n;j++)
		{
			if(max<dp[i][j])
				max=dp[i][j];
		}
	printf("%d\n",max+1);
	return 0;
}