---
title: "数字三角形"
created: 2025-11-28
tags:
  - 算法
---

# 数字三角形

## 题目 [数字三角形](https://www.acwing.com/problem/content/900/)

![[image-339c7e1b.png]]

## 思路分析

![[image-b385014d.png]]

求一条路径 累加最大值

首先完全可以用dfs做 得到所有方案 再遍历取得最大的答案

又可以从dp的角度思考——省去递 直接推

把某点之前的点当已知答案 用已知的答案推出当前点

所以为了方便表示状态 我们给每个点进行编号

![[image-189041ca.png]]

就可以用f[i][j]表示 所有从起点 走到i，j这个点的所有走法 的距离最大值

我们发现每个点 不过就是两种情况得到

![[image-7a4dd5d7.png]]

我们这个f[3,2]（起点到3,2的距离最大值 要么是从起点到2,1的最大值中加上这个当前点1 要么是从起点到2,2的最大值 加上这个点1）

所以也就是说 当前点的状态 要么就从左上角的转移过来 要么从右上角的转移过来

可以画出dp分析图

![[image-cbbdf92e.png]]

再考虑特殊情况 因为是从左上右上转移过来 不可避免的就会碰到左上或者右上没有值的情况（三角形的边缘）

![[image-d89399b6.png]]

此时就得置成-inf吧 才能保证答案是从有值的那一边转移过来

那么就得初始化成这样

![[image-cc43c665.png]]

那么最后的答案应该就在最下面这一层

![[image-75ff13e9.png]]

f[n][1-m] 还得从这里面遍历找到一个最大的作为真正答案

（为什么？考虑实际含义 f[n][1]表示到n,1的所有路径长的最大值 f[n][2]表示到n，2的…… 只是针对一个点来说的 那为什么背包问题可以直接取nm——从这个写法出发其实他也得这样做
只不过加了一点额外考虑 从前n个物品里选5个 自然会比在前n个物品里选3个得到的价值更大吧 所以直接在nm里取答案）

发现还不如就干脆从下面开始做起 推到上面去

![[image-53915fc3.png]]

这样答案就在1,1的地方了 不需要遍历一整行 甚至连边界情况也不需要考虑了

因为都是从左下和右下转移过来的

那么这时状态转移方程就变成了

f[i,j]=max(f[i+1][j]+a[i][j],f[i+1][j+1]+a[i][j]);

(另外提一句 背包问题一开始也是这样分析的 只不过它那种选与不选用这种图形很难描述出来 我们这里也不过只是借助图像了解坐标 实际上就可以把图形省略掉
直接从集合的角度来去思考这个状态转移问题 y总的dp分析法确实nb）

解决完这道题后 拓展一个内容

![[image-a8ad2d2c.png]]

每走到一个点 就选它下一个能选的最大的点行不行（可能因为这里是找最大 如果找最小 没负权的话应该是可行的）

其实这个问题 把树拓展到图

就是我们的最短路问题中迪杰斯特拉算法和spfa算法的比较问题了

当时就提到了 迪杰斯特拉基于贪心 而spfa基于动态规划

现在应该更理解了这个问题吧

spfa其实就是这个问题的一个拓展吧 这里每个点只能从两个孩子得到 而图中 就不像二叉树一样只能从两边得到了 在图中 加入该点后 看总长度是否变化
每步都基于全局考虑 而非逐步最优的贪心

## 代码实现

从上往下推

```cpp
#include<bits/stdc++.h>
using namespace std;

const int N=510,INF=1e9;
int a[N][N];
int f[N][N];
int n;

int main()
{
    cin>>n;
    //下标从1开始 因为有i-1操作 防止0-1越界
    for(int i=1;i<=n;i++){
        for(int j=1;j<=i;j++){
            cin>>a[i][j];
        }
    }
    //从0开始 因为要在外围多加一层-inf
    for(int i=0;i<=n;i++){
        for(int j=0;j<=i+1;j++){
            f[i][j]=-INF;
        }
    }

    //起点是确定的权重吧
    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;
    return 0;
}
```

从下往上推

```cpp
#include<bits/stdc++.h>
using namespace std;

const int N=510;
int f[N][N];
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-1;i>=1;i--){
        for(int j=1;j<=i;j++){
            f[i][j]=max(f[i+1][j+1],f[i+1][j])+f[i][j];
            //                右下               左下
        }
    }

    //顶部就是答案
    cout<<f[1][1];
    return 0;
}
```

## 同类题型

## 视频讲解

---
⬅️ [[摘花生|摘花生]] 🏠 [[00-刷题理模型]] ➡️ [[数字三角形模型练习|数字三角形模型练习]]