题目描述

给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

//倒序dp不需要处理边界问题
#include<iostream>
#include<cmath>
#include<algorithm>
int a[510][510];
int n;
using namespace std;
int main()
{
    cin>>n;
    for(int i = 1;i <= n;i++)
    {
        for(int j = 1;j <=i;j++)
        {
            cin>>a[i][j];
        }
    }
    for(int i = n;i >= 1;i--)
        for(int j = i;j >= 1;j--)
            a[i][j]=max(a[i+1][j],a[i+1][j+1])+a[i][j];
    cout<<a[1][1];
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla