滑雪（记忆化搜索）

题目 题解

记忆化搜索模板题。

记忆化搜索的核心： ① 本质是带剪枝的深搜。 ② 当某点的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
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 > m;
	for (int i = 1;i  a[i][j];
	
	for (int i = 1;i