8.记忆化搜索

记忆化搜索就是对于某个子问题的解可能会被多次用到，那么就把子问题的解保存起来，以后用到的时候直接用，不用再计算一遍，以滑雪这道题为例，多条路径可能经过同一个点，那么就把这个点的值保存起来，只计算一次。

AcWing 901. 滑雪

实现思路：

搜狗截图20220329203216.png

  • 状态表示f[i][j]，表示从点(i,j)出发的最长路径长度

  • 集合划分可分为四种情况：从点(i,j)出发

    • 向左走到(i,j-1)，状态转换为f[i][j-1]+1
    • 向右走到(i,j+1)，状态转换为f[i][j+1]+1
    • 向上走到(i-1,j)，状态转换为f[i-1][j]+1
    • 向下走到(i+1,j)，状态转换为f[i+1][j]+1

  • 注意：在向某个方向走时要判断是否走出边界以及所走的方向的值是否小于当前位置的值

  • 没有给出固定出发点，所以要遍历每个点为起点出发

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=310;
int f[N][N],h[N][N];
int n,m;
int dx={1,0,-1,0},dy={0,1,0,-1};//表示四个可走的方向

//以x,y为起点的最长路径长度 返回f[x][y]
int dp(int x,int y){
    if(f[x][y] !=-1) return f[x][y];//如果该点已经计算过了，就直接返回答案
    f[x][y]=1;//初始路径长度为1
    for(int i=0;i<4;i++){//四个方向选择
        int xx=x+dx[i],yy=y+dy[i];//选择一个方向走
        if(xx>=1 && xx<=n && yy>=1 && yy<=m && h[x][y]>h[xx][yy])
            f[x][y]=max(f[x][y],dp(xx,yy)+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];
    memset(f,-1,sizeof f);//初始化f
    
    //以每个点为起点遍历
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            res=max(res,dp(x,y));
    cout<<res<<endl;
    return 0;
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。