dp——poj1088（Description）

dp可以按照思想大致分为两种，一种是递推的形式，一种是递归的形式（记忆化搜素）。

比如求这个题因为无法知道从哪个点开始，所以只能用递归的形式，因为有一个回溯的过程。

但是很多题目既可以用递推也可以用递归。

最简单举例：Fibonacci数列

递推形式：f[1]=1;f[2]=1;f[n]=f[n-1]+f[n-2];(3-->n)

递归形式：n=<2;return 1; f(n)=f(n-1)+f(n-2);

 #include <iostream>

 #include <cstring>

 #include <string>

 #include <map>

 #include <set>

 #include <algorithm>

 #include <fstream>

 #include <cstdio>

 #include <cmath>

 #include <stack>

 #include <queue>

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 using namespace std;

 const double Pi=3.14159265358979323846;

 typedef long long ll;

 const int MAXN=+;

 const int dx[]={,,,-};

 const int dy[]={,-,,};

 const int INF = 0x3f3f3f3f;

 const int NINF = 0xc0c0c0c0;

 const ll mod=1e9+;

 int dp[MAXN][MAXN];

 int s[MAXN][MAXN];

 int m,n;

 int f(int a,int b)

 {

     if(dp[a][b]!=) return dp[a][b];

     for(int i=;i<;i++)

     {

         int x=a+dx[i];

         int y=b+dy[i];

         if(x>=&&x<=m&&y>=&&y<=n&&s[x][y]<s[a][b])

         {

             dp[a][b]=max(dp[a][b],f(x,y)+);

         }

     }

     return dp[a][b];

 }

 int main()

 {

     scanf("%d%d",&m,&n);

     for(int i=;i<=m;i++)

         for(int j=;j<=n;j++)

             {

                 scanf("%d",&s[i][j]);

                 dp[i][j]=;

             }

     int ans=;

     for(int i=;i<=m;i++)

         for(int j=;j<=n;j++)

         {

             ans=max(ans,f(i,j));

         }

     cout <<ans+<<endl;

     return ;

 }