傳說(shuō)中經(jīng)典DP，記憶化搜索？其實(shí)就是在一個(gè)二維數(shù)組中求一個(gè)最長(zhǎng)下降的子序列的長(zhǎng)度。
其實(shí)就是從每個(gè)元素開(kāi)始找以它為起始點(diǎn)的最長(zhǎng)下降子序列，當(dāng)遞歸到該點(diǎn)比周圍所有的點(diǎn)都小時(shí)即返回，
自低向上的方法，注意與廣搜不同，廣搜是自頂向下。
以后每個(gè)點(diǎn)的計(jì)算都可以用到以前的結(jié)果，因?yàn)檫@是無(wú)后效性的？這就是傳說(shuō)中的記憶化？
#include <stdio.h>
#include <string.h>
#define N 105
#define INF 1 << 28
int r, c;
int h[N][N], a[N][N];
int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int dfs(int x, int y)
{
if(a[x][y]) return a[x][y];
int max = 0, t;
for(int i = 0; i < 4; i++)
{
int xx = x + dir[i][0];
int yy = y + dir[i][1];
if(xx < 0 || xx >= r || yy < 0 || yy >= c) continue;
if(h[xx][yy] < h[x][y])
{
t = dfs(xx, yy);
max = max > t ? max : t;
}
}
a[x][y] = max + 1;
return max + 1;
}
int main()
{
int ans;
while(~scanf("%d %d", &r, &c))
{
for(int i = 0; i < r; i++)
for(int j = 0; j < c; j++)
{
scanf("%d", &h[i][j]);
a[i][j] = 0;
}
ans = -INF;
for(int i = 0; i < r; i++)
for(int j = 0; j < c; j++)
{
int t = dfs(i, j);
if(t > ans) ans = t;
}
printf("%d\n", ans);
}
return 0;
}