本文共 1381 字，大约阅读时间需要 4 分钟。

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

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

输入格式

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

输出格式

数据范围

5

7

3 8

8 1 0

2 7 4 4

4 5 2 6 5

输出样例：

30

思路

用闫氏DP，从下往上分析，因为如果从上往下找最长路径，就一定会要考虑到边界问题。把三角形中的每一个点用二维坐标来表示，这样结果数组中每一个点只要取从他下一层左节点和右节点中路径长度更大的那一个在加上自己原本得值即为从下往上到这个点得最长路径。

代码

#include
   
    #include
    
     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];  //f作为结果数组，最下面一行    for(int i=n-1;i>0;i--){
   					//的点结果肯定是本身        for(int j=1;j<=n;j++){
               f[i][j] =max(f[i+1][j],f[i+1][j+1])+w[i][j];        }									//当前点下一层左边和右边的点    }										//中路径更长的那一个加上本身    cout<
     
      <
     
    
   

优化代码

实际上可以发现w数组得存在是多余得，可以直接用一个f数组来存储

#include
   
    #include
    
     using namespace std;const int N=510;int n;int f[N][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>0;i--){
           for(int j=1;j<=n;j++){
               f[i][j] += max(f[i+1][j],f[i+1][j+1]);        }    }    cout<
     
      <
     
    
   

转载地址：https://blog.csdn.net/qq_45380840/article/details/112463360 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！