洛谷 “滑雪”P1434题解——记忆化搜索
在洛谷 “滑雪” P1434题解——DP中介绍了这道题的动态规划解法，下面介绍的则是记忆化搜索。事实上我也是dp的初学者，我决定用这道经典的题目来体会dp和记忆化的正真思路。未来会对dp以及记忆化搜索进行总结。
首先先亮出喜闻乐见的大爆搜。
12345678910111213141516171819202122232425262728#include <bits/stdc++.h>using namespace std;int n,m;int i,j;int d[105][105],a[105][105];int maxn;void dfs(int dep,int x,int y){maxn=max(dep,maxn);//取最大深度 //四个方向进行遍历if (a[x+1][y]<a[x][y]) dfs(dep+1,x+1,y);if (a[x-1][y]<a[x][y]) dfs(dep+1,x-1,y);if (a[x][y+1]<a[x][y]) dfs(dep+1,x,y+1);if (a[x][y-1]<a[ ...
洛谷 \"滑雪\" P1434题解——DP
作为洛谷弱狗的第一篇题解，那必须要写的详细一点/doge
还记得初二的时候听老师讲动态规划，完全就没听懂，现在上了高中，再重温动态规划，似乎有了新的感悟。
先说整体做法：优先队列+线性动态规划 42ms
由于x和y的范围在1~100区间，所以直接暴力搜索一定会超时。
一个格子中可以有四个方向分别滑过来:[x+1][y], [x-1][y], [x][y+1],[x][y-1]。先分别判断这四个方位是否比中心的格子低。如果比中心的格子低，那么有如下的动态转移方程：
d[i][j]=max{d[i][j],d[x+1][y]+1,d[x-1][y]+1,d[x][y+1]+1,d[x][y-1]+1}
但是动态规划要考虑无后效性，如果只是挨个遍历，那么结果肯定是错误的。因此要维护一个从小到大的优先队列。从低的点算起，那么对于后续高的点没有影响。
其余请浏览代码注释部分。
123456789101112131415161718192021222324252627282930313233343536373839404142434445#include <bits ...
