Skip to main content

洛谷 P1216 [IOI 1994] 数字三角形 Number Triangles

给定一个 rr 行的数字三角形（r≤1000r \leq 1000），需要找到一条从最高点到底部任意处结束的路径，使路径经过数字的和最大。每一步可以走到当前点左下方的点或右下方的点。在下面这个示例中，最优路径是 7→3→8→7→57 \to 3 \to 8 \to 7 \to 5。

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