AcWing 901. 滑雪（记忆化搜索）

题目链接

https://www.acwing.com/problem/content/903/

思路

我们定义 f [ i ] [ j ] f[i][j] f[i][j]表示以 ( i , j ) (i,j) (i,j)作为起点的滑行最远距离，由于我们至多只有四个方向滑行且要求只能朝低处滑行，那么我们的状态也最多从四个方向转移过来，于是我们使用搜索在递归的时候处理边界，然后回溯的时候不断地更新 f [ i ] [ j ] f[i][j] f[i][j]地值，详情请看代码

代码

#include
using namespace std;

const int N = 3e2+10;
int a[N][N],f[N][N];
int n,m;

int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};


int dfs(int x,int y){
    if(f[x][y]) return f[x][y];
    f[x][y] = 1;
    for(int i = 0;i  0 && ny > 0 && nx >m;
    for(int i = 1;i a[i][j];
            
    int ans = 0;
    for(int i = 1;i