Algorithm8.3 DFS 记忆化搜索
[TOC]
DFS 记忆化搜索
用于相邻依赖 => 涂色：相邻的不能相同；连续递增/连续递减
搜索的形式+dp的存储思想，把dp数组融合到dfs搜索的过程中。
[模版] 记忆化搜索 - 优化重复递归调用
https://www.luogu.com.cn/problem/P1464
题目大意：纯粹的重复递归调用，极限的话20 * 20 * 20次不同的计算要被一直算，如果可以记录下来，那么这么多次运算只需要算一遍。
1、用dp来记录下来每次的递归结果，也就是return之前先给dp附上值。return dp=w();
2、注意return的时候，看看边界条件，特判条件放在前面先return；递归条件放后面return
#include <iostream>
using namespace std;
#define maxn 25
typedef long long ll;
ll ta, tb, tc, dp[maxn][maxn][maxn];
ll dfs(int a, int b, int c) {
if (a <= 0 || b <= 0 || c <= 0) return 1;
if (a > 20 || b > 20 || c > 20) return dfs(20, 20, 20);
if (dp[a][b][c]) return dp[a][b][c];
if (a < b && b < c) return dp[a][b][c] = dfs(a, b, c-1) + dfs(a, b-1, c-1) - dfs(a, b-1, c);
else return dp[a][b][c] = dfs(a-1, b, c) + dfs(a-1, b-1, c) + dfs(a-1, b, c-1) - dfs(a-1, b-1, c-1);
}
int main() {
while (scanf("%lld%lld%lld", &ta, &tb, &tc) && !(ta==-1 && tb==-1 && tc==-1))
printf("w(%lld, %lld, %lld) = %lld\n", ta, tb, tc, dfs(ta, tb, tc));
return 0;
}
记忆化搜索
https://www.luogu.com.cn/problem/P1434
题目大意：地图中最长的路线，没有固定起点。
1、没有固定起点，就代表要所有点都做起点去算一遍。所以计算的总成本就是算一个点的成本*总共的点数=>多次重复计算，所以用记忆化搜索来储存减少运算量
2、先递归满足往深层次拓展的点，然后拓展完成之后，再来更新dp数组。dfs(nx, ny);然后dp[x][y] = max(dp[x][y], dp[nx][ny]+1);
#include <iostream>
using namespace std;
#define maxn 205
int r, c, mp[maxn][maxn], dp[maxn][maxn], ans, dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // dp[i][j]这个点开始的最长连续下降的长度
int dfs(int x, int y) {
if (dp[x][y]) return dp[x][y];
dp[x][y] = 1;
for (int i = 0; i < 4; ++i) {
int nx = x+dir[i][0], ny = y+dir[i][1];
if (nx >= 0 && nx < r && ny >= 0 && ny < c && mp[nx][ny] < mp[x][y]){
dfs(nx, ny);
dp[x][y] = max(dp[x][y], dp[nx][ny]+1);
}
}
return dp[x][y];
}
int main() {
scanf("%d%d", &r, &c);
for (int i = 0; i < r; ++i)
for (int j = 0; j < c; ++j)
scanf("%d", &mp[i][j]);
for (int i = 0; i < r; ++i)
for (int j = 0; j < c; ++j)
ans = max(ans, dfs(i, j));
printf("%d\n", ans);
return 0;
}