递归——深度优先搜索（DFS）——以滑雪问题为例（自顶而下）
1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9
-
-
输出描述:输出最长区域的长度.
-
5 5 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9
1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9
依此输入为例（以21所在位置为起点）
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=105,mod=1e9+7;
int a[N][N];
int n,m;
int tmp;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int h[N][N];//记录坐标(i,j)的答案，以（i，j）为起点的路径最长多少
int dfs(int x,int y){//以(x,y)为起点的遍历
int mx=0;
if(h[x][y])return h[x][y];// 记录为0的路径避免重复计算
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]<a[x][y]){//递归出口：找不到更低的去处
mx=max(mx,dfs(nx,ny));//递归体：只要能在周围找到能去的路径，递归调用去找能去路径的最大值
}
}
return h[x][y]=mx+1;//最终求出周围路径最大值+1就是（x,y)为起点的最长滑坡长度
}
// dfs： 这个算法会尽可能深的搜索树的分支 ,#include<cstdio>
#include<algorithm>
using namespace std;
const int N=105,mod=1e9+7;
int a[N][N];
int n,m;
int tmp;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int h[N][N];//记录坐标(i,j)的答案，以（i，j）为起点的路径最长多少
int dfs(int x,int y){//以(x,y)为起点的遍历
int mx=0;
if(h[x][y])return h[x][y];// 记录为0的路径避免重复计算
for(int i=0;i<4;i++){
int nx=x+dx[i],ny=y+dy[i];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]<a[x][y]){//递归出口：找不到更低的去处
mx=max(mx,dfs(nx,ny));//递归体：只要能在周围找到能去的路径，递归调用去找能去路径的最大值
}
}
return h[x][y]=mx+1;//最终求出周围路径最大值+1就是（x,y)为起点的最长滑坡长度
}
// dfs： 这个算法会尽可能深的搜索树的分支 ,时间复杂度为O（N）
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dfs(i,j);
}
}
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
ans=max(ans,h[i][j]);
}
}
printf("%d\n",ans);
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]);
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dfs(i,j);
}
}
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
ans=max(ans,h[i][j]);
}
}
printf("%d\n",ans);
}
五、递归思想总结
-
归纳假设：一个节点为起点的最深路径为周围节点最深路径加一
-
-
f(x,y)：路径的长度
-
f（x,y）==1 当四周找不到更低的地方（无处可去）(递归出口)
-
f(x,y)==max(f(x-1,y),f(x+1,y),f(x,y+1),f(x,y-1))+1（递归体）
-
六、感悟：
先将大问题分解成一个基础问题+一个小一层级问题，并用递归模型表示出来，利用图文结合方法加快效率。最后落地。
