89分倒数第二个TLE，能不能优化

lzyzon @ 2023-08-29 12:07:17

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

by NSZBD_dklmq12 @ 2023-08-29 12:16:38

2^500,咋优化啊

可用动态规划

by lujunxuan123 @ 2023-08-29 12:17:48

@NSZBD_dklmq12 他加记忆化了

by lujunxuan123 @ 2023-08-29 12:19:13

@lzyzon 开个O2试试吧

by lujunxuan123 @ 2023-08-29 12:23:02

@lzyzon 实在不行就只能dp了

by NSZBD_dklmq12 @ 2023-08-29 12:25:28

@lujunxuan123 O2还是T了

by myzzym @ 2023-08-29 12:34:50

有些f[x][y]是0的情况导致多次便利，开个数组记录就好了

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

by myzzym @ 2023-08-29 12:36:17

你这记忆化得不标准

by lzyzon @ 2023-08-29 16:08:25

谢谢大佬们，已经过了

by lzyzon @ 2023-08-29 16:08:55

此贴完