题目链接：POJ 1088
题意：
给一个二维数组，每个数组元素是一个整数表示高度，每次从一个点可以上下左右四个方向移动，但是必须是高度下降方向，问最长的下降长度是多少？
例如：25->24->23->......->3->2->1，长度是25.
分析：
求最长下降子序列问题。使用DP+递归。
DP状态转移方程：//DP[i][j]表示从（i，j）位置出发的最长下降子序列
DP[i][j]=max(DP[x][y])+1;其中（x，y）是（i，j）上下左右四个方向上的合法下标
注意点：
- 记忆化搜索，避免重复计算
- x，y合法性判断
- return时应+1（本身一个元素）
CODE:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
using namespace std;const int maxn = 105;
int height[maxn][maxn], dp[maxn][maxn];
//height[i][j]表示二维数组中下标为(i,j)的高度，dp[i][j]是相应最长下降子序列
int dir[4][2] = { {-1,0},{1,0},{0,1},{0,-1} };
int x, y, r, c;int DP(int row, int col)
{if (dp[row][col] > 0) return dp[row][col];//已经计算过了int tmpmax = 0;//这里只能初始化为0，而不能是-1for (int i = 0;i < 4;i++)//4个方向查找最大值{x = row + dir[i][0];y = col + dir[i][1];if (x < 0 || y < 0 || x >= r || y >= c || height[x][y] >= height[row][col]) continue;//下标越界或者高度不满足下降条件tmpmax = max(tmpmax, DP(x, y));//取四个方向中的最大值}return tmpmax + 1;//结果要算上(row,col)本身这一个元素
}int main()
{
#ifdef LOCALfreopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout);
#endifwhile (cin >> r >> c){memset(dp, -1, sizeof(dp));for (int i = 0;i < r;i++)for (int j = 0;j < c;j++)cin >> height[i][j];int ans = -1;for (int i = 0;i < r;i++){for (int j = 0;j < r;j++){dp[i][j] = DP(i, j);ans = max(ans, dp[i][j]);} }cout << ans << endl;}return 0;
}