【前言】

今天是刷题打卡第62天！

记得加油哦。

原题：数字三角形（递推、简单DP）

原题链接：[USACO1.5][IOI1994]数字三角形 Number Triangles - 洛谷

题目描述： 

输入格式：

第一个行一个正整数 n ,表示行的数目。

后面每行为这个数字金字塔特定行包含的整数。

输出格式：

单独的一行,包含那个可能得到的最大的和。

数据范围：

1 ≤ n ≤ 1000，三角形数字值在 [0,100] 范围内。 

示例:

输入：

  

   

    

     

    
    

     

      5
     
    
   

    

     

    
    

     

      7
     
    
   

    

     

    
    

     

      3 8
     
    
   

    

     

    
    

     

      8 1 0
     
    
   

    

     

    
    

     

      2 7 4 4
     
    
   

    

     

    
    

     

      4 5 2 6 5 
     
    
  
 

输出：

30
 

思路：

本题采用倒推的方式：

假设func[i][j]表示的是从 i, j 到最后一层的最大路径之和

当从顶层沿某条路径走到第i层向第i+1层前进时，我们的选择是沿其下两条可行路径中最大数字的方向前进，所以找出递推关系：func[i][j] += max(func[i+1][j],func[i+1][j+1])；
注意：func[i][j]表示当前数字的值，func[i+1][j]和func[i+1][j+1]分别表示从i+1,j、i+1,j+1到最后一层的最大路径之和；
最终func[0][0]就是所求

代码执行：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int func[1005][1005] = {0};
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    int n = 0;
     
    
   

    

     

    
    

     
    scanf("%d", &n);
     
    
   

    

     

    
    

     
    int i = 0;
     
    
   

    

     

    
    

     
    int j = 0;
     
    
   

    

     

    
    

     
    for(i = 0; i < n; i++)
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     
        for(j = 0; j <= i; j++)
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     
            scanf("%d", &func[i][j]);
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    //假设func[i][j]表示的是从i, j到最后一层的最大路径之和
     
    
   

    

     

    
    

     
    //找出递推关系：func[i][j]+=max(func[i+1][j],func[i+1][j+1]);
     
    
   

    

     

    
    

     
    //func[i][j]表示当前数字的值，func[i+1][j]和func[i+1][j+1]分别表示从i+1,j、i+1,j+1到最后一层的最大路径之和
     
    
   

    

     

    
    

     
    //最终func[0][0]就是所求
     
    
   

    

     

    
    

     
    for(i = n - 2; i >= 0; i--)
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     
        for(j = 0; j <= i; j++)
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     

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

    

     

    
    

     

              }
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    printf("%d\n", func[0][0]);
     
    
   

    

     

    
    

     
    return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

结语

今天是刷题打卡第62天！

加油吧少年。

文章来源: bit-runout.blog.csdn.net，作者：安然无虞，版权归原作者所有，如需转载，请联系作者。

原文链接：bit-runout.blog.csdn.net/article/details/122009547