文章目录

记忆化搜索

1.数塔问题

【动规：递归求解】

递推方程：

不难发现，最后一层的点到最后一层的最大距离即为自己对应的值a[n - 1][y]，这个就是问题的边界。从后往前推，观察发现当前点的状态只与正下方和右下方的状态有关，因此得出递推式（状态转移方程）：d[i][j] = a[i][j] + max(a[i+1][j],a[i + 1][j + 1])

既然有了上述的递推式，我们直到递归和递推其实是相互的，因此递推可以改写成递归的形式。

#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 500 + 10;int a[N][N];int d[N][N];int n;int ans = -1e9;// 求从点（x,y）开始，走到最后一层，经过数字的最大和。int fun(int x, int y){if(x == n) return a[x][y];// 最后一层的解就是自己return a[x][y] + max(fun(x + 1, y), fun(x + 1, y + 1));// 如果不是最后一行就递归计算}int main(){cin >> n;for(int i = 1; i <= n; i ++)for(int j = 1; j <= i; j ++)cin >> a[i][j];cout << fun(1, 1);return 0;}

缺点：

效率太低了，并不是因为递归就效率低，而是因为存在了大量的重复计算。（类比递归式的斐波那契数列）

递归存在着大量不必要的重复计算，，递归的层数就越多，算的就越多，重复的计算更多！

【动规：记忆化搜索】

上述方法，存在着大量的重复计算，那我们如何在使用递归的情况下去优化，免去那些不必要的重复计算呢？

如上图，我们在求d[2][1]的时候就把d[3][2]计算过了，而我们再求d[2][2]的时候，又把d[3][2]再计算了一次，这就造成了重复计算？那如何解决呢？

在计算d[2][1]的时候就把d[3][2]计算过了，可以把d[3][2]用一个数组存下来，当再次需要d[3][2]时，就不需要再去递归求解了，直接用数组中备份过的数据就行——这就是记忆化搜索！

动规：记忆化搜索：

求解每一个点的值，先判断该点的值是否曾经求解过，如果曾经求解过，直接拿过来使用；如果没求解过，递归求解，并存储该解！将计算过的值存储到一个数组中如何判断是否求解过呢？——做标记判断

【代码实现】

#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 500 + 10;int a[N][N];int d[N][N];int n;int ans = -1e9;//动规，记忆化搜索：先将d数组初始化为-1，方便判断有没有求解过int fun(int x, int y){if(x == n) return a[x][y];// 最后一层的解就是自己else{if(d[x][y] != -1) return d[x][y];// 曾经求解过else {//求解（x,y)点走到底层经过的数字和的最大值，并存储d[x][y] = a[x][y] + max(fun(x + 1, y), fun(x + 1, y + 1));return d[x][y];}}}int main(){cin >> n;for(int i = 1; i <= n; i ++)for(int j = 1; j <= i; j ++)cin >> a[i][j];memset(d, -1, sizeof d);cout << fun(1, 1);return 0;}

当然数塔问题也可以用递推还有dfs深搜（会爆炸）的方式来求解。

2.滑雪

dfs深搜代码如下：

#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 310;int h[N][N];int n, m;int ans = -1e9;int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};int dfs(int x, int y, int len){if(len > ans) ans = len;for(int i = 0; i < 4; i ++){int a = x + dx[i], b = y + dy[i];if(a >= 0 && a < n && b >= 0 && b < m && h[x][y] > h[a][b]){dfs(a, b, len + 1);}}}int main(){scanf("%d%d", &n, &m);for (int i = 0; i < n; i ++ )for (int j = 0; j < m; j ++ )scanf("%d", &h[i][j]);memset(dp, -1, sizeof dp);for (int i = 0; i < n; i ++ )for (int j = 0; j < m; j ++ ){int len = 0;dfs(i, j, len);}printf("%d", ans + 1);return 0;}

dfs爆搜会超时！

本来是一个dfs的过程，遍历所有的位置，找到从当前位置往下走的最大路径，再取最大值，单纯递归深搜的缺点就在于：存在着大量的重复计算。因此我们可以用一个数组，将把遍历过的位置往下走的路径的最大值进行记录，再次遇到直接拿来使用即可，这就是记忆化搜索(空间换时间)。

思路：dfs + 记忆化

​ 遍历每个点作为起点

​ 然后检测该点四周的点 如果可以滑动到其他的点

​ 那么该点的最大滑动长度 就是其他可以滑到的点的滑动长度+1

【代码实现】

#include <iostream>#include <cstring>#include <algorithm>using namespace std;const int N = 310;int h[N][N];int dp[N][N]; 记录从（x，y）点能滑雪的最长距离 int n, m;int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};//递归 + 记录结果 == 记忆化搜索（DP的一种）int dfs(int x, int y){if(dp[x][y] != -1) return dp[x][y];// 被计算过了，直接拿，不用再次计算dp[x][y] = 1;// 初始化for(int i = 0; i < 4; i ++){int a = x + dx[i], b = y + dy[i];if(a >= 0 && a < n && b >= 0 && b < m && h[x][y] > h[a][b]){dp[x][y] = max(dp[x][y], dfs(a, b) + 1);}}return dp[x][y];}int main(){scanf("%d%d", &n, &m);for (int i = 0; i < n; i ++ )for (int j = 0; j < m; j ++ )scanf("%d", &h[i][j]);memset(dp, -1, sizeof dp);int res = 0;for (int i = 0; i < n; i ++ )for (int j = 0; j < m; j ++ )res = max(res, dfs(i ,j));printf("%d", res);return 0;}

总结

记忆化深搜，其实就是对递归dfs暴力的一种优化，将计算过的记录下来，避免重复计算。记忆化深搜也属于DP的一种！

最常见的DP就是那种寻找状态转移方程（递推式）递推求解的了。