题目：uva10285 - Longest Run on a Snowboard（记忆化搜索）

题目大意：给出N * N的矩阵，要求找到一条路径，路径上的值是递减的，求这样的路径的最长长度。

解题思路：记忆话搜索。因为要求最长的路径那么就需要将所有的这样的路径找出，但是直接dfs会超时的。对于同一个位置，从这个点出发的最长路径长度是固定的。所以在找的时候就要将这个位置的最长路径算出来并且保存下来。一开始还担心会走回头路就是一直兜圈子。但是后面发现能往右走就不可能在从右边的那个位置走回去，因为路径上的值是要求递减的。

dp【x】【y】代表从x，y这个位置开始能够走的最长的路径长度。

代码：

#include 
  
   
#include 
   
     const int N = 105; const int M = 4; const int dir[M][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}}; int G[N][N]; int dp[N][N]; char name[N * 10]; int r, c; int Max (const int a, const int b) { return a > b? a: b; } int DP (int x, int y) { int& ans = dp[x][y]; if (ans != -1) return ans; int newx, newy; for (int i = 0; i < M; i++) { newx = x + dir[i][0]; newy = y + dir[i][1]; if (newx < 0 || newx >= r || newy < 0 || newy >= c) continue; if (G[x][y] > G[newx][newy]) ans = Max (ans, DP (newx, newy) + 1); //从这个位置开始四个方向的最长长度取最大值 } if (ans == -1) //这个点走不出去 ans = 1; return ans; } int main () { int t; scanf ("%d", &t); while (t--) { scanf ("%s%d%d", name, &r, &c); for (int i = 0; i < r; i++) for (int j = 0; j < c; j++) scanf ("%d", &G[i][j]); memset (dp, -1, sizeof (dp)); int ans = -1;
   
  

		for (int i = 0; i < r; i++) 从每个位置开始走都是有可能的取得最长路径
			for (int j = 0; j < c; j++)
				ans = Max (ans, DP(i, j));
		printf ("%s: %d\n", name, ans);	
	}
	return 0;
}