[动态规划](8)记忆化搜索

滑雪

模板题:901. 滑雪 - AcWing题库

image-20210707181329637

思路:

  • 使用记忆化数组,记录每个点的最大滑动长度
  • 遍历每个点作为起点
  • 然后检测该点四周的点,如果可以滑动到其他的点
  • 那么该点的最大长度就是可以其他滑倒的点的滑动长度+1
  • 由于滑雪必须是滑到比当前低的点,所以不会存在一个点多次进入的问题

思维导图:

image-20210707181052214

代码:

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n, m;
const int N = 310;
int g[N][N];//矩阵
int f[N][N];//状态转移
int dx[4]{ -1,0,1,0 };
int dy[4]{ 0,1,0,-1 };//偏移向量

int dp(int x, int y) {
    int& v = f[x][y];//引用,v全部为f[x][y]的值

    if (v != -1) return v;//如果这个点已经被算过了 则返回 v 
    v = 1;//v为1,代表为一步,初始条件

    for (int i = 0; i < 4; i++) {//枚举四个方向选取最大值
        int a = x + dx[i], b = y + dy[i];
        if (a >= 1 && a <= n && b >= 1 && b <= m && g[x][y] > g[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 >> g[i][j];

    memset(f, -1, sizeof f);

    int res = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            res = max(res, dp(i, j));

    cout << res << endl;
    return 0;

}

本文链接:

https://nullcode.fun/157.html
1 + 8 =
快来做第一个评论的人吧~