[记忆化搜索] 滑雪(模板题+记忆化搜索)

0. 前言

动态规划问题可以使用记忆化搜索 + 递归来求解。也是 dfs 优化的方式，两者本无区别。

1. 记忆化搜索模板题

重点： 记忆化搜索、递归实现 dp

思路：

• 状态定义：
  • f[i][j]：所有从 (i, j) 开始滑的路径的最大值
• 状态转移：
  • 分类依据：滑的方向就是上下左右四个方向，当下一个位置的高度低于当前高度的是个更新状态即可
    • 显然，计算 f[i][j] 时，需要提前计算得到前一个转移过来的状态，然后再这样一直往前找，是具备依赖关系的。注意，当这些状态的依赖关系构成一个环的时候就无法正确得到结果了。显然，若 a>b>c>d>a 这种路径是不存在的，所以一定可以正确求解，不会构成死循环。 即，它是一定存在一个拓扑序的
• 状态转移方程：if (a >= 1 && a <= n && b >= 1 && b <= m && h[a][b] < h[x][y]) 则，f[x][y] = max(f[x][y], dp(a, b) + 1);。其中 a,b 为四个方向的下一个位置的下标
• 状态初始化：下标从 1 开始，避免边界情况的特判。f[x][y] = 1 自己滑自己，起步为 1。取 max 操作，故 f 数组全部初始化为 -1(其实在此不初始化 f 也行，因为每次都会给 f[x][y] 赋为 1，但养成一个好习惯，还是老老实实初始化)
• 返回答案： max f[i][j]

dp 就是一个 DAG(有向无环图)。

这里的记忆化搜索乍一看和 dfs 也没什么两样，都是方向数组加 dfs 的过程。但是 if (f[x][y] != -1) return f[x][y]; 的存在，就是大大减少了 dfs 暴搜的计算量。若当前遍历状态已经计算过了，就不必再重复计算下面的状态了，这就充分体现了记忆化搜索的优势。且这也是 dp 问题的一个最鲜明特点：带记忆化的暴力搜索。

当然，不论是线性 dp、区间 dp 这样的采用循环进行状态计算。还是树形 dp、记忆化搜索这样的采用递归实现 dp，现在还没啥太大感悟，但是有大佬讲 dp 都是可以采用递归来进行实现的，且这更加契合正常的思考方式，就连状态转移方程都是一个递归式子的形式。希望在日后多多刷题中能悟到！

代码：

#include <iostream>
#include <cstring> 
#include <algorithm>

using namespace std;

const int N = 305;

int n, m;
int h[N][N];
int f[N][N];

int dx[4] = {-1, 0, 1, 0}, 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 = 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 && h[a][b] < h[x][y])
            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 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;
}

dfs 部分超时代码：

#include <iostream>
#include <cstring> 
#include <algorithm>

using namespace std;

const int N = 305;

int n, m;
int h[N][N];
int res = -1;

int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

void dfs(int x, int y, int len) {
    if (res < len) res = len;
    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 && h[a][b] < h[x][y])
            dfs(a, b, len + 1);
    }
}

int main() {
    cin >> n >> m;
    
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >> h[i][j];
            
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            int len = 1;
            dfs(i, j, len);
        }
        
    cout << res << endl;
    
    return 0;
}