动态规划-数字三角形

//数字三角形，动态规划(没用递归)
/*
    从朴素递归到各种优化，以及动态规划具体讲解blog：
	https://www.cnblogs.com/LYLtim/p/4286150.html
 
    本题后来由我自己重新做了一遍，并且AC了。 与原答案不同也只是在第二步的双重for循环中。
    后来发现，这是《算法入门经典》里面的第二种方法——递推计算，时间复杂度和记忆化搜索一样的。
*/


#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
int main()
{
    int n;  int a[101][101];
    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=1; j<i ; j++)
            a[i-1][j]=max(a[i][j],a[i][j+1])+a[i-1][j];

    cout << a[1][1];
    return 0;
}