数字三角形

看到该题我首先想到了DFS然后回顾了排列数字的问题，但是这个像图的遍历，
不知道该怎么做,如何才能把每一条路径都遍历一遍呢？
本题应用DFS也可以做，枚举，但是可能会超时，可以一试

这里学习到一种新的知识：DP

该题的这种做题思路值得我学习，我看到这道题先想我该怎么遍历全部的元素
然后如何加和求最大值，想了半天也没有结果，做题思路非常值得我学习！！！！

方法一：从上往下遍历

代码：

#include<iostream>
using namespace std;
const int N=510,y=-2e9;
int f[N][N];
int a[N][N];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cin>>a[i][j];

        }
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<=i+1;j++){
            f[i][j]=y;
        }
    }
    f[1][1]=a[1][1];
    for(int i=2;i<=n;i++){
        for(int j=1;j<=i;j++){
            f[i][j]=a[i][j]+max(f[i-1][j-1],f[i-1][j]);
        }
    }
    int res=y;
    for(int i=1;i<=n;i++){
        res=max(res,f[n][i]);
    }
    cout<<res;
    return 0;
}

方法二：从下往上遍历

#include<iostream>
using namespace std;
const int N=510;
int y=-2e9;
int f[N][N];
int a[N][N];
int main(){

    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cin>>a[i][j];
            f[i][j]=y;
        }
    }
    for(int i=1;i<=n;i++){
        f[n][i]=a[n][i];
    }
    for(int i=n-1;i>=1;i--){
        for(int j=1;j<=n;j++)
        f[i][j]=a[i][j]+max(f[i+1][j],f[i+1][j+1]);
    }
    cout<<f[1][1];

}