巴斯卡三角形

背景知識是:

  • 邊界的位置數值為 1
  • 除了邊界,新的每個位置是上一列左右總和

公式:

  • n 層有 n 個元素
  • 第一個元素與最後一個元素數值為 1 (a[n][0] = 1 && a[n][n-1] = 1)
  • n > 2 層,第 k 元素為上列左右總和: a[n][k] = a[n-1][k-1] + a[n-1][k] (n > 1 && n < k)

知道背景知識後,實作上並不困難。

遞迴版本:

閱讀小提示:numRows-1 表示現在這列,上一列要 -2。

如果看不慣遞迴的同學可以看看迴圈版本:

不過這其實是 O(n³)/O(n) ,並不是 O(n²),因為 Java 的 ArrayList.get() indexing 是 O(n) ,儘管我們可以簡單暫存 lastRow 也於事無補,因為 left 與 right 仍有類似的問題。

所以我們可以改用 primitive array 取代 ArrayList 來維持 O(n²)/O(2n):

p.s. 其實 ArrayList.add() 也是 O(n) ,要另外拉出去做才算打完收工,不然改用 LinkedList 吧

另外其實我們也可以觀察出來巴斯卡三角形是鏡像的,所以理論上還可以把複雜度減半: O(n n/2) ,不過也微乎其微,就不用特別做了。