从数字三角形的顶部（如图，第一行的5表示行数）到底部有很多条不同的路径。对于每条路径，把路径上面的数加起来可以得到一个和，且！！！！！！！！！

==================================================================================

==================================================================================

你有一次机会可以把任何一个数重复加一遍。

==================================================================================

==================================================================================

和最大的路径称为最佳路径。你的任务就是求出最佳路径上的数字之和。

==================================================================================

==================================================================================

题目看仔细！！若AC欢迎公开题解（不知道怎么加的看右上角）！！

==================================================================================

==================================================================================

如果空间复杂度不够去4832，同一道题但空间复杂度要求不高（但是4832白银）

第一行：一个数，表示行数。

接下来n行为数塔

一个数即最优结果

5

1

1 3

1 1 3

1 1 1 3

7 1 1 1 3

18

三角形行数不大于1000。最大和不大于maxlongint

#include<cstdio>#include<algorithm>using namespace std;const int N=1e3+1;int n,a[N][N],f[N][2];int main(){    scanf("%d",&n);    for(int i=1;i<=n;i++){        for(int j=1;j<=i;j++){            scanf("%d",&a[i][j]);        }    }    for(int i=n;i;i--){        for(int j=1;j<=i;j++){            f[j][1]=max(max(f[j][0],f[j+1][0])+2*a[i][j],max(f[j][1],f[j+1][1])+a[i][j]);            f[j][0]=max(f[j][0],f[j+1][0])+a[i][j];        }    }    printf("%d",max(f[1][0],f[1][1]));    return 0;}