LeetCode 熱題 100 | 118. 楊輝三角

大家好，今天我們來解決一道經典的算法題——楊輝三角。這道題在 LeetCode 上被標記為簡單難度，要求生成楊輝三角的前 numRows 行。楊輝三角是一個經典的組合數學問題，每一行的數字都是其正上方和正左上方的數字之和。下面我將詳細講解解題思路，并附上 Python 代碼實現。

---

問題描述

給定一個非負整數 numRows，生成楊輝三角的前 numRows 行。在楊輝三角中，每個數字是其正上方和正左上方的數字之和。

示例 1：

輸入: numRows = 5
輸出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2：

輸入: numRows = 1
輸出: [[1]]

提示：

• 1 <= numRows <= 30

---

解題思路

核心思想

1. 逐行生成：

   • 每一行的第一個和最后一個數字都是 1。
   • 中間的數字可以通過上一行的相鄰兩個數字相加得到。

2. 動態規劃：

   • 使用一個二維列表 triangle 來存儲楊輝三角的每一行。
   • 每一行的生成依賴于上一行的值。

---

Python代碼實現

def generate(numRows):# 初始化楊輝三角triangle = []for i in range(numRows):# 每一行的第一個和最后一個數字都是 1row = [1] * (i + 1)# 計算中間的數字for j in range(1, i):row[j] = triangle[i - 1][j - 1] + triangle[i - 1][j]# 將當前行加入楊輝三角triangle.append(row)return triangle# 測試示例
numRows1 = 5
numRows2 = 1result1 = generate(numRows1)
result2 = generate(numRows2)print(result1)  # 輸出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
print(result2)  # 輸出: [[1]]

---

代碼解析

1. 初始化楊輝三角：

   • 使用一個二維列表 triangle 來存儲每一行。

2. 逐行生成：

   • 每一行的第一個和最后一個數字都是 1。
   • 中間的數字通過上一行的相鄰兩個數字相加得到。

3. 動態規劃：

   • 每一行的生成依賴于上一行的值，因此我們逐行構建楊輝三角。

---

復雜度分析

• 時間復雜度：O(numRows2)，其中 numRows 是楊輝三角的行數。我們需要逐行生成每一行的數字。
• 空間復雜度：O(numRows2)，用于存儲楊輝三角的每一行。

---

示例運行

示例 1

輸入: numRows = 5
輸出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2

輸入: numRows = 1
輸出: [[1]]

---

總結

通過逐行生成的方法，我們可以高效地構建楊輝三角。這種方法直觀且易于實現，適合大多數場景。希望這篇題解對大家有所幫助，如果有任何問題，歡迎在評論區留言討論！

關注我，獲取更多算法題解和編程技巧！