问题:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1088思路1:
这题是前段时间微软笔试的最后一道大题，当时没想太多，直接简单DFS，没想到会超时，结果嘛直接被BS了...太菜啊
我们从最优解开始分析:
设p[1]--p[2]--p[3]...--p[n]即为最长的一条路径L, p[i]=(xi, yi)
对于该路径L中的一个点p[i], 可以这样来理解: 到达点p[i]的最长路径是到达点p[i-1]的最长路径加1， 并且height(p[i-1])大于height(p[i])
因此，我们可以
先将输入地图按照高度从高到低排序，然后从头开始依次求出最长路径需要注意的一点：
下面代码的第8行需要设置max为1，而不是0， 因为该点可能是最高点(peek)
1 int
2 dp()
3 {
4 int total = row*col;
5 int i, j, x, y, sx, sy, td, max, longest=1;
6 distance[points[0].x][points[0].y] = 1; //highest point
7 for(i=1; i<total; i++) {
8 max = 1; //max should be set 1, in case points[i] is a peek
9 x = points[i].x;
10 y = points[i].y;
11 for(j=0; j<4; j++) { //four directions
12 sx = x+dx[j];
13 sy = y+dy[j];
14 //points[sx*col+sy] is a higher point around points[i]
15 if(can_go(sx, sy) && points[i].height<height[sx*col+sy]) { //distance[sx][sy]>0 indicates (sx, sy) a higher point
16 td = distance[sx][sy]+1;
17 max = max > td ? max : td;
18 }
19 }
20 distance[x][y] = max;
21 longest = longest > max ? longest : max;
22 }
23 return longest;
24 }
思路2:
备忘录方法
这里我们换一种看待该问题的方式
该题有一个很自然的想法，那就是依次枚举每个点，计算从每个点出发的最长路径，最后求这些最长路径的最大值即可
从一个点p[i]出发的最长路径是: 从其上下左右四个点出发的最长路径的最大值加1
备忘录方法真的非常好用，而且理解起来也较动态规划简单呵呵，原本超时的代码只要稍加修改就可以AC了
1 int
2 dp_memory(int x, int y)
3 {
4 if(opt[x][y] != 0) //memory, simple but powerful
5 return opt[x][y];
6
7 int max = 0;
8 int i, sx, sy, tmp;
9 for(i=0; i<4; i++) { // four directions
10 sx = x + dx[i];
11 sy = y + dy[i];
12 if(sx>=0 && sx<=row-1 && sy>=0 && sy<=col-1 && map[sx][sy]<map[x][y]) {
13 tmp = dp_memory(sx, sy);
14 max = max > tmp ? max : tmp;
15 }
16 }
17 opt[x][y] = max+1;
18 return opt[x][y];
19 }
1 for(i=0; i<row; i++)
2 for(j=0; j<col; j++) {
3 tmp = dp_memory(i, j);
4 max = max > tmp ? max : tmp;
5 }
6