这篇文章上次修改于 694 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

本文共 631 个字，阅读时长 ≈ 2 分钟

AcWing 898. 数字三角形

题面：

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

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

这个图看着不直观，让我们转化一下：

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

这样更符合我们二维数组的排序。要从顶部走到最底下一层，只能向下走或右下走，求到底层路径上的数字之和最大。

只能往两个地方走，所以可以很简单的写出状态转移方程（之前的不写是因为我不会我懒）$\text{f}[i][j]=\max(\text{f}[i+1][j],\text{f}[i+1][j+1])+\text{f}[i][j]$ 这里我用的是倒序，从最底层往上找，这样不用判断边界更方便一点。

用一个数组是因为数组的原值在改变后只会使用一次（上一层的max），所以直接用读入的数组进行动态规划即可。

#include<iostream>
using namespace std;
int f[1510][1510];
int n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=i;++j) cin>>f[i][j];
    }
    for(int i=n;i>=1;--i){
        for(int j=i;j>=1;--j)
            f[i][j]+=max(f[i+1][j],f[i+1][j+1]);
    }
    cout<<f[1][1]<<endl;
    return 0;
}