用记忆#8过不了，求助！！

lxl2012 @ 2024-07-08 11:33:01

#include<bits/stdc++.h>
using namespace std;
long long r,a[1001][1001],jilu[1001][1001];
long long ta(long long i,long long j){
    if(i > r){
        return 0;
    }
    if(!jilu[i][j]) jilu[i][j] = max(ta(i + 1,j),ta(i + 1,j + 1)) + a[i][j];
    return jilu[i][j];
}
int main(){
    cin>>r;
    for(int i = 1;i <= r;i ++){
        for(int j = 1;j <= i;j ++){
            cin>>a[i][j];
        }
    }
    cout<<ta(1,1);
}

by ATION001 @ 2024-07-08 11:39:17

@lxl2012 这题这么写就行了，而且不开long long也能过。

#include<bits/stdc++.h>
using namespace std;
int a[1005][1005],dp[1005][1005];
int n;
int dfs(int x,int y){
    if(dp[x][y]>-1){
        return dp[x][y];
    }
    if(x==n){
        dp[x][y] = a[x][y];
    }else{
        dp[x][y] = max(dfs(x+1,y),dfs(x+1,y+1))+a[x][y];
    }
    return dp[x][y];
}
int main(){
    fill(dp[0],dp[0]+1005*1005,-1);
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<=i;j++){
            cin>>a[i][j];
        }
    }
    cout<<dfs(0,0);
    return 0;
}