题目描述
记忆化搜索
滑雪:
从任意一点开始滑,能向上下左右四个方向滑动(前提是该方向的高度比当前高度低),求出滑雪路线路经长度的最大值
动态规划
f[i][j]
状态表示:
集合:起点为(i,j)的所有路径的集合
属性:路径的max
状态计算:
划分依据,第一步是向上下左右哪个方向滑动的
第一步向右滑:f[i][j]=f[i][j+1]+1
第一步向左滑:f[i][j]=f[i][j-1]+1
第一步向下滑:f[i][j]=f[i+1][j]+1
第一步向上画:f[i][j]=f[i-1][j]+1
但并不是每一步都能走,只有当下面一步的高度小于当前高度才行
注:能进行记忆化搜索的前提是没有环
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m;
const int N = 310;
int h[N][N];//每个点的高度
int f[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dfs(int x,int y)
{
if(f[x][y]!=-1) return f[x][y];
f[x][y]=1;
for(int i=0;i<4;i++)
{
int a=x+dx[i],b=y+dy[i];
if(a>=1 && a<=n && b>=1 && b<=m && h[x][y]>h[a][b])
{
f[x][y]=max(f[x][y],dfs(a,b)+1);
}
}
return f[x][y];
}
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>h[i][j];
}
}
int res=0;
memset(f,-1,sizeof f);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
res=max(res,dfs(i,j));
}
}
cout<<res<<endl;
return 0;
}