记忆化搜索

实际上规划问题可以用递归求解

滑雪

只能走比当前低的格子，求最多走多少格

状态表示

f[i][j]存以第 i 行第 j 个为起点的所有可能路径 属性是 MAX

状态计算

分类：

• 向右
• 向左
• 向上
• 向下 这样可以分为不重不漏的四类

在能走的路径中，（以向下走为例）f[i][j] = f[i+1][j] + 1 遍历所有点，因为有限定条件（往低处走），所以不会有回路，相互依赖导致不能求解

记住每点最小值为 1

实现

#include <iostream>
#include <algorithm>
#include <cstring>
 
using namespace std;
 
const int N = 330;
 
int h[N][N];
int f[N][N];
 
//偏移量
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
 
int n, m;
 
int dp(int i, int j)
{
    //引用 V = f[i][j]
    int &V = f[i][j];
    if(V != -1) //走过
        return V;
        
    //最少是自己一格
    V = 1;
    for(int k = 0; k < 4; k ++)
    {
        int a = i + dx[k], b = j + dy[k];
        
        if(a >= 1 && a <= n && b >= 1 && b <= m && h[i][j] > h[a][b])
            V = max(V, dp(a, b) + 1);
    }
    
    return V;
}
 
 
int main()
{
    cin >> n >> m;
    
    for(int i = 1; i <= n;  i ++)
        for(int j = 1; j <= m; j ++)
            cin >> h[i][j];
    
    //赋初值，用于判断当前值有没有走过        
    memset(f, -1, sizeof f);
    
    int ans = 0;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            ans = max(ans, dp(i, j));
            
    cout << ans << endl;
    
    return 0;
}