The Triangle

数字三角形：这应该是最简单的动态规划题了。
解题思路：题目要求所有路径中最大的，可以考虑从后面入手，第(i,j)的最大值，有两个来源，一个是从上直接下来，还有就是从斜边下来,即（i-1，j）和（i-1,j-1）中取最大值。然后定义一个变量用来记录最大值。最后输出这个最大值就行了！

#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
int main(){
    int n;
    int a[105][105];
    memset(a,0,sizeof(a));
    int dp[105][105];
    memset(dp,0,sizeof(dp));
    cin>>n;
    int maxim =0;
    for(int i=1; i <= n; i++){
        for(int j =1; j <= i; j++ ){
            cin >> a[i][j];
              dp[i][j]=max(dp[i-1][j], dp[i-1][j-1]) + a[i][j];
              if(dp[i][j] > maxim)
                 maxim = dp[i][j];
        }
    }

    cout << maxim << endl;

    return 0;
}