POJ 1088 DP

//经典DP题 一个点一个点的进行搜索
#include<cstdio>
#include<cstring>
using namespace std;
#define MAX(a,b) (a)>(b)?(a):(b)
int n,m;
int dx[4]= {-1,0,1,0},dy[4]= {0,1,0,-1};
int opt[105][105],a[105][105];
bool ok(int i,int j)
{
    return (i>=1&&i<=n&&j>=1&&j<=m);
}
int dp(int i,int j)
{
    int k;
    if(opt[i][j]>0) return opt[i][j];
    for(k=0;k<4;k++)
    {
        if(ok(dx[k]+i,dy[k]+j))
        {
            if(a[i][j]>a[i+dx[k]][j+dy[k]])
            opt[i][j]=MAX(opt[i][j],dp(i+dx[k],j+dy[k])+1);  //opt[i][j]代表第i行j列能够得到的最大值
        }
    }
    return opt[i][j];
}
int main()
{
    int i,j;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
       for(i=0;i<=n;i++)
        for(j=0;j<=m;j++)
            opt[i][j]=0;
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=m; j++)
            {
                scanf("%d",&a[i][j]);
            }
        }
        int ans=0;
        for(i=1; i<=n; i++)
        {
            for(j=1; j<=m;j++)
            {
                ans=MAX(ans,dp(i,j));
            }
        }
        ans++;
        printf("%d\n",ans);
    }
    return 0;
}

POJ 1088 DP,布布扣,bubuko.com

POJ 1088 DP

原文：http://blog.csdn.net/littlefool5201314/article/details/22945387