滑雪——记忆化搜索

滑雪

题意：

在二维数组中找到一条数字逐渐减小的最长的路径，输出路径长度

思路：

确定状态：

dp[i] [j] 表示从（i，j）开始走的最长路径的长度

原问题：

从（1，1）到（n，m）任意一点开始走的最长路径的长度

状态转移方程：

dp[i] [j] = max{dp[i - 1] [j] + 1, dp[i + 1] [j] + 1, dp[i] [j - 1], dp[i] [j + 1]}

显然for循环没法一次性解决，之前的题都是按一定顺序，如从1到n，而现在你有四个方向，循环跑i，j的时候，你需要知道[i - 1] [j], [i + 1] [j],[i] [j + 1], [i] [j - 1]的值，可你不一定有他们的值，所以没法跑之前的dp，那我们就使用秘技：记忆化搜索

搜这个i，j的点的时候，判断一下这个点有没有值，如果有值就直接返回该值，如果没有，就去算他周围的四个点的，求最大值，并返回，注意判断是否出界

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 1000000 + 7
#define endl '\n'
#define mod 1e9+7;
typedef  long long ll ;
//不开longlong见祖宗！
//ios::sync_with_stdio(false);
//cin.tie(0); cout.tie(0);
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;
        ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, m, ans;
int tr[105][105], dp[105][105];

bool judge(int x, int y){
    if(x < 1 || x > n || y < 1 || y > m)return false;
    return true;
}

int calc(int i, int j){
    if(dp[i][j] != 0)return dp[i][j];
    dp[i][j] = 1;
    if(tr[i - 1][j] < tr[i][j] && judge(i - 1, j))dp[i][j] = max(dp[i][j], calc(i - 1, j) + 1);
    if(tr[i + 1][j] < tr[i][j] && judge(i + 1, j))dp[i][j] = max(dp[i][j], calc(i + 1, j) + 1);
    if(tr[i][j - 1] < tr[i][j] && judge(i, j - 1))dp[i][j] = max(dp[i][j], calc(i, j - 1) + 1);
    if(tr[i][j + 1] < tr[i][j] && judge(i, j + 1))dp[i][j] = max(dp[i][j], calc(i, j + 1) + 1);
    return dp[i][j];
}

int main(){
    cin>>n>>m;
    for(int i = 1; i <= n; ++i)
    for(int j = 1; j <= m; ++j){
        tr[i][j] = IntRead();
    }
    for(int i = 1; i <= n; ++i)
    for(int j = 1; j <= m; ++j){
        calc(i, j);
    }
    ans = -1e9;
    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;
}