求助，记忆化搜索不知道怎么写

JWWJ0101 @ 2021-05-20 20:59:24

#include<iostream>
using namespace std;
int N=0;
int d[999][999]={};
int k[999][999]={};
int MAX(int n,int m){

    if(n==N){
        return d[n][m];
    }
    int a=MAX(n+1,m)+d[n][m];
    int b=MAX(n+1,m+1)+d[n][m];

    if(a>b){
        return k[n][m]=a;
    }else{
        return k[n][m]=b;
    }
}
int main(){
    cin>>N;
    for(int i=0;i<999;i++){
        for(int j=0;j<999;j++){
            k[i][j]=-1;
        }
    }

    for(int i=1;i<=N;i++){
        for(int j=1;j<=i;j++){
            cin>>d[i][j];
        }
    }
    cout<< MAX(1,1);
}

by Wildcxj @ 2021-05-20 21:01:10

额，DP他不香吗？

by ikkkkkkk @ 2021-05-20 21:32:08

这道题用dp写好点吧

by Wildcxj @ 2021-05-20 21:37:23

嘿，我突然发现我居然做过IOI的题目！珂朵莉万岁！！

by Enterprise_E @ 2021-08-21 15:57:30

@JWWJ0101 这道题用DP好点

记忆化搜索代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1005;
int a[MAXN][MAXN],f[MAXN][MAXN];
int dfs(int x,int y){
    if(f[x][y]==-1){
        if(x==n)f[x][y]=a[x][y];
        else f[x][y]=a[x][y]+max(dfs(x+1,y),dfs(x+1,y+1);
    }
    return f[x][y];
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;++i){
        for(int j=0;j<i;++j){
            cin>>a[i][j];
        }
    }
    for(int i=0;i<n;++i){
        for(int j=0;j<i;++j){
            f[i][j]=-1;
        }
    }
    dfs(1,1);
    cout<<f[1][1]<<endl;
    return 0;
}