记忆化搜索

记忆化搜索理解：在暴力搜索的基础上，记录了搜索的状态，从别的状态搜索过来后不用再重复搜索，减少了时间复杂度。
https://www.acwing.com/problem/content/903/

#include<bits/stdc++.h>
using namespace std;
const int N=301;
int m[N][N];
int dp[N][N];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int r,c;
int s(int x,int y)
{
    int &v = dp[x][y];
    if(v!=0) return v;
    v =1;
    for(int i=0;i<4;i++)
    {
        int nx =x+dx[i];
        int ny =y+dy[i];
        if(nx>=0 && nx<r && ny>=0&&ny<c && m[nx][ny]<m[x][y])
        {
            v=max(v,s(nx,ny)+1);
        }
    }
    return v;
}
int main(void)
{
    scanf("%d%d",&r,&c);
    for(int i=0;i<r;i++)
    {
        for(int j=0;j<c;j++)
        {
            scanf("%d",&m[i][j]);
        }
    }
    int ans =0;
    for(int i=0;i<r;i++)
    {
        for(int j=0;j<c;j++)
        {
            ans = max(ans,s(i,j));
        }
    }
    printf("%d\n",ans);
}

https://leetcode.cn/problems/number-of-increasing-paths-in-a-grid/

class Solution {
public:
    int n;
    int m;
    int mod;
    int dx[4] ={0,1,-1,0};
    int dy[4] = {1,0,0,-1};
    vector<vector<int>>dp;
    int dfs(int x,int y,vector<vector<int>>&grid)
    {
        int& v = dp[x][y];
        if(v!=0) return v;
        v = 1;
        for(int i=0;i<4;i++)
        {
            int nx= x+dx[i];
            int ny = y+dy[i];
            if(nx>=0 && nx<m && ny>=0 && ny<n && grid[nx][ny]>grid[x][y])
            {
                v =(v+dfs(nx,ny,grid))%mod;
            }
        }
        return v;
    };
    int countPaths(vector<vector<int>>& grid) {
        int ans =0;
        m =grid.size();
        n = grid[0].size();
        mod = 1e9+7;
        vector<vector<int>>dp(m,vector<int>(n,0));
        this->dp = dp;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                ans =(ans+dfs(i,j,grid))%mod;
            }
        }
        return ans;
    }
};