数字三角形

原题链接

AcWing 898.数字三角形

题目描述

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

        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

题目分析

动态规划分析-闫式思考法

从集合角度来考虑DP问题，用 f[i,j] （状态表示）来表示所有从 (1,1) 走到 (i,j) 的路线（集合），并记录更新所有路线中所经数字和的最大值（属性）。
i，j的划分如下图所示。

题目分析可知，只能向左下走或向右下走，则对于任一点 (i,j) 来说，上一个点只能来自左上或右上（状态划分）。据此进行状态计算。

状态计算可知，f[i,j] 取为二者的最大值。

初始化问题

对于很多的边界问题，多初始化一些f值（-INF）,避免边界问题。

完整代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N=510;
const int INF=1e9;  //负无穷
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=0;i<=n;i++){
        for(int j=0;j<=i+1;j++){
            f[i][j]=-INF;
        }
    }
    //起始点(1,1)不由左上、右上得到，而直接初始化为a[1][1]
    f[1][1]=a[1][1];
    //状态计算
    for(int i=2;i<=n;i++){
        for(int j=1;j<=i;j++){
            f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j]);
        }
    }
    int res=-INF;
    //结果选取最后一行的最大值
    for(int i=1;i<=n;i++) res=max(res,f[n][i]);
    cout<<res<<endl;
    return 0;
}