文章目录

• 前言
• 一、动态规划
• 二、AcWing 901. 滑雪
• • 本题解析
  • AC代码
• 三、时间复杂度

---

前言

复习acwing算法基础课的内容，本篇为讲解基础算法：动态规划——记忆化搜索，关于时间复杂度：目前博主不太会计算，先鸽了，日后一定补上。

---

一、动态规划

动态规划（Dynamic Programming，DP）是求解决策过程最优化的过程，个人认为是目前接触的所有算法里最绕的…

这里的题目的解题方法来自于：y总的闫氏dp分析法

---

二、AcWing 901. 滑雪

本题链接：AcWing 901. 滑雪
本博客提供本题截图：

本题解析

这里的代码很像 BFS 那边的内容，事实上记忆化搜索(DP)确实是 DFS之剪枝与优化的一种方式

AC代码

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

using namespace std;

const int N = 310;

int n, m;
int g[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];
    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 && g[x][y] > g[a][b])
            v = max(v, dp(a, b) + 1);
    }

    return v;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            scanf("%d", &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));

    printf("%d\n", res);

    return 0;
}

---

三、时间复杂度

关于动态规划——记忆化搜索的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。