啊米诺斯，数字三角形TLE了，求改

cheyifeng @ 2024-12-08 09:35:31

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

by TODAYS @ 2024-12-08 09:45:30

#include<bits/stdc++.h>
using namespace std;
int a[1005][1005],c[1005][1005],n;
int func(int i,int j){
    if(c[i][j]>-1)return c[i][j];
    if(i==n) c[i][j] = a[i][j];
    else c[i][j]=max(func(i+1,j),func(i+1,j+1))+a[i][j];
    return c[i][j];
}
int main(){
    memset(c,-1,sizeof(c));
    cin>>n;
    for(int i=1;i<=n;i++)for(int j=1;j<=i;j++)cin>>a[i][j];
    cout<<func(1,1);
    return 0;
}

by amnsteng @ 2024-12-08 09:48:20

@cheyifeng不是都在写吗

by cheyifeng @ 2024-12-08 10:14:36

谢了哈