C++算法数字三角形

数字三角形

题目

如图所示，存在一个包含n层的数字三角形结构。从最顶端开始，每个节点均可向左下方或右下方的节点移动，直至抵达最底层。目标是确定一条路径，使得该路径上所有数字之和达到最大值。

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

具体内容请参见898. 数字三角形 - AcWing题库

题解

正序

设f[x][y]表示位于第x行、第y列位置的数值，且该数值与前一位置的数字之和为当前行中最大值，则其计算方式如下：
f[x][y]=a[x][y]+max(f[x-1][y-1] ,f[x-1][y])
在进行决策时，只需关注边界条件即可，具体包括：

• 左边界情况：f[x][y]=a[x][y]+f[x-1][y].
• 右边界情况：f[x][y]=a[x][y]+f[x-1][y-1].

最终可得出完整的二维数组f[n][y]，通过比较该数组中的所有元素