最大路徑和基本資訊

最大路徑和是一種演算法,用於找出路徑,使得該路徑的元素(節點)之和大於任何其他路徑。

例如,我們有一個三角形,如下所示。

        3
      7   4
    2   4   6
  8   5   9   3

在上面的三角形中,找到具有最大總和的最大路徑。答案是,3 + 7 + 4 + 9 = 23

為了找到解決方案,我們一如既往地瞭解 Brute-Force 方法。Brute-Force 方法適用於這 4 行三角形,但考慮一個 100 或 100 行以上的三角形。因此,我們不能使用 Brute-Force 方法來解決這個問題。

讓我們轉向動態程式設計方法。

演算法:

對於三角形或二叉樹中的每個節點,最大路徑可以通過節點進行四種方式。

  1. 僅限節點
  2. 通過 Left Child + Node 的最大路徑
  3. 通過右子節點的最大路徑
  4. 通過右子節點的最大路徑+通過右子節點的最大路徑。

最大路徑和演算法示例:

StackOverflow 文件

空間輔助: O(n)
時間複雜度: O(n)