动态规划——记忆化搜索DP

以901. 滑雪 - AcWing题库为例

记忆化搜索和DFS：

DFS：在某个方向上滑雪滑倒不能滑为止，然后再回溯继续滑，直到以所有点为起始点全部遍历完

记忆化搜索：用f[i,j]记录，以某点开始滑的最大路径，保证不重复搜索

f[][]二维数组初始化的时候最好统一赋值为-1，如果不进行初始化直接用0判断，此题可以，可是如果遇到一些记忆化搜索的问题要求方案数的时候，初始化是0可能会导致个别情况计算出来的恰好结果是0时，却被认为未遍历过，因此统一赋值为-1就没错了

python版本：

N = 310
high = [[0] * N for _ in range(N)]
f = [[-1] * N for _ in range(N)]
dx = [-1,0,1,0]
dy = [0,1,0,-1]
n,m=map(int,input().split())
for i in range(1,n+1):
    ll=list(map(int,input().split()))
    high[i][1:m+1]=ll
def dp(x,y):
    if f[x][y]!=-1:
        return f[x][y]
    f[x][y]=1
    for i in range(4):
        a=x+dx[i]
        b=y+dy[i]
        if 1<=a<=n and 1<=b<=m and high[x][y]>high[a][b]:
            f[x][y]=max(f[x][y],dp(a,b)+1)
            
    return f[x][y]
        
        
def DP():
    res = 0
    for i in range(1,n+1):
        for j in range(1,m+1):
            res = max(res,dp(i,j))
    return res
print(DP())

c++版本：

#include #include 
#include using namespace std;
const int N = 310;
int f[N][N], w[N][N];
int n, m; 
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int dp(int x, int y)
{
    int &t = f[x][y];
    if (t != -1) return t;
    t = 1;
    for(int i = 0; i < 4; i ++)
    {
        int a = dx[i] + x, b = dy[i] + y;
        if (a >= 1 && a <= n && b >= 1 && b <= m && w[a][b] < w[x][y]) {
            t = max(t, dp(a, b) + 1);
        }
    }
    return t;
}
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            scanf("%d", &w[i][j]);
    memset(f, -1, sizeof f);
    int res = 0;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            res = max(res, dp(i, j));
    cout << res << endl;
    return 0;
}