文章目录
前言
一、动态规划
二、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; }
三、时间复杂度
关于动态规划——记忆化搜索的时间复杂度以及证明，后续会给出详细的说明以及证明过程，目前先鸽了。
