滑雪（记忆化搜索）

题目

题解

记忆化搜索模板题。

记忆化搜索的核心：
① 本质是带剪枝的深搜。
② 当某点的dp已赋值时，返回该值。
③ 其他情况进行深度搜索。

模板：

dfs(u点) {
	if u点的 dp 已经有值了 : return u点的 dp 值
	else 说明第一次到达u，则为u的 dp 赋初值
	for 遍历四个方向，确定合理的下一个位置 :
		通过深搜dfs返回的值更新u点的 dp 值
	return u点的 dp 值
}

main() {
	for 遍历全部起点s :
		ans = max/min{ans, dfs(s)}
}

代码

// 滑雪 记忆化搜索 
#include<bits/stdc++.h>
using namespace std;
const int N = 310;

int dir[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};
int n, m;
int dp[N][N], a[N][N], ans;

int dfs (int x, int y) {
	if (dp[x][y] != 0) return dp[x][y]; // 如果(x,y)的dp已经有值了，说明(x,y)这个点的价值已经固定了！之后再遇到要计算该点价值的情况直接返回即可。
	if (dp[x][y] == 0) dp[x][y] = 1; // 如果dp为0，说明第一次计算该点，所以赋值为1，表示从任意一个点开始滑雪，高度至少为1。
	for (int k = 0;k < 4;k ++) { // 遍历四个方向
		int tx = x + dir[k][0], ty = y + dir[k][1]; // 下一个位置
		if (tx < 1 || ty < 1 || tx > n || ty > m || a[x][y] <= a[tx][ty]) continue; 
		// 如果超界或者当前位置的高度不超过下一个位置的高度，则continue
		// a[x][y] <= a[tx][ty]这个条件保证了不需要设置一个bool数组控制哪些位置已经遍历过（需要自己理解）
		dp[x][y] = max(dp[x][y], dfs(tx, ty) + 1); // 更新(x,y)位置（也就是当前位置）的价值；dfs返回的就是(tx,ty)的价值
	}
	return dp[x][y]; // 返回计算结果
}

int main ()
{
	cin >> n >> m;
	for (int i = 1;i <= n;i ++)
		for (int j = 1;j <= m;j ++)
			cin >> a[i][j];
	
	for (int i = 1;i <= n;i ++) 
		for (int j = 1;j <= m;j ++)
			if (dp[i][j] == 0) 
				dp[i][j] = dfs(i, j),
				ans = max(ans, dp[i][j]); // 确定一个最大的即可。只要是计算完的dp，一定是最终的dp，这时对记忆化搜索的理解。
	
	cout << ans << endl;
	
	return 0;
}