需要协助算法才能找到DAG中的最大路径

Question

假设我有这个有向无环图(DAG),其中每个节点(除了底行中的节点除外)有一个有向边到它下面的两个节点:

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

我需要找到通过此DAG的路径,其中节点权重的总和最大化.您只能从此树中的节点向左或向右对角移动.因此,例如,7,3,8,7,5将在此树中给出最大路径.

输入文件包含以这种方式格式化的DAG

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

我的问题是,什么算法最好找到最大路径,以及如何在C++中表示这个树？

节点权重是非负的.

Answer 1

我用一个矢量向量来表示这个三角形int.

从底行开始,比较每对相邻的数字.拿一个较大的一个并将其添加到该对上方的数字:

 5 3             13  3
  \
7 8 6  becomes  7  8  6
^ ^

                  13 3               13 11
                     /
Next iteration   7  8  6   becomes  7  8  6  etc.
                    ^  ^

按照自己的方式到达顶部,完成后,三角形的尖端将包含最大的总和.