题目内容

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

输入格式

第一行包含整数n，表示数字三角形的层数。

接下来n行，每行包含若干整数，其中第 i 行表示数字三角形第 i 层包含的整数。

输出格式

输出一个整数，表示最大的路径数字和。

数据范围

1≤n≤500 ,
−10000≤三角形中的整数≤10000

输入样例

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

输出样例

30

题解

对本题思考发现，如果从上往下思考，会导致每个数考虑从左边下来还是右边下来，这样导致一些特判的发生，会写很多边界判定代码。若从下往上思考，则每个数考虑从哪个方向上来的，这样就不需要很多特判了，除了最后一行的数之外，其他行均有下方两个方向上来。

一、状态表示——f(i,j)
1、集合
从底向上走到（i，j）所有路线的集合
2、属性
路线数字和最大值
二、状态计算（集合划分）
max{f(i+1,j)+w(i,j),f(i,j+1)+w(i,j)}

代码

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 510;

int n;

int w[N][N],f[N][N];

int main(){
    cin >> n;
    for(int i = 1; i<=n;i++){
        for(int j = 1;j<=i;j++){
            cin >> w[i][j];
        }
    }
    
    for(int i = 1; i <= n; i++) f[n][i] = w[n][i];
    for(int i = n - 1; i ; i--){
        for(int j = 1; j<=i; j++){
            f[i][j] = max(f[i+1][j]+w[i][j],f[i+1][j+1]+w[i][j]);
        }
    }
    cout << f[1][1] << endl;
    return 0;
}