118. Pascals Triangle

Easy

Description

給定非負整數 numRows，生成帕斯卡三角形的前 numRows 行。在帕斯卡三角形中，每個數字是其正上方兩個數字之和。

Example:

Input: numRows = 5 Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

Intuition#

核心思路：逐行生成，每行的首尾為 1，中間元素等於上一行對應位置兩個元素之和。

第 i 行有 i + 1 個元素
triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]（當 j 不是首尾時）

Approaches#

1: 逐行生成（使用上一行）#

概念: 維護上一行的結果，逐行計算新行
時間複雜度: O(numRows^2) - 總元素數為 1+2+…+numRows
空間複雜度: O(numRows^2) - 儲存所有行

class Solution {
    fun generate(numRows: Int): List<List<Int>> {
        val result = mutableListOf<List<Int>>()
        for (i in 0 until numRows) {
            val row = MutableList(i + 1) { 1 }
            for (j in 1 until i) {
                row[j] = result[i - 1][j - 1] + result[i - 1][j]
            }
            result.add(row)
        }
        return result
    }
}

⭐2: 逐行生成（簡潔寫法）#

概念: 同樣逐行生成，但利用 Kotlin 的函式風格使程式碼更簡潔
時間複雜度: O(numRows^2)
空間複雜度: O(numRows^2)

class Solution {
    fun generate(numRows: Int): List<List<Int>> {
        val triangle = mutableListOf<List<Int>>()
        for (i in 0 until numRows) {
            val row = MutableList(i + 1) { 1 }
            for (j in 1 until i) {
                row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j]
            }
            triangle.add(row)
        }
        return triangle
    }
}

補充：數學公式法（組合數）

第 i 行第 j 個元素等於組合數 C(i, j)，可以用乘法遞推計算，不需要參考上一行。

class Solution {
    fun generate(numRows: Int): List<List<Int>> {
        val result = mutableListOf<List<Int>>()
        for (i in 0 until numRows) {
            val row = mutableListOf<Int>()
            var value = 1L
            for (j in 0..i) {
                row.add(value.toInt())
                value = value * (i - j) / (j + 1)
            }
            result.add(row)
        }
        return result
    }
}

🔑 Takeaways#

Pattern: 帕斯卡三角形是 DP 的經典範例，每個狀態由上一行推導
關鍵技巧: 首尾直接設 1，中間用上一行推算；組合數遞推 C(n,k) = C(n,k-1) * (n-k+1) / k 是避免溢出的好方法