題目描述

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

楊輝三角解析

在這個詳解中，我們將使用 ASCII 圖形來說明楊輝三角的構建過程，包括逐行添加新的行的過程。這個圖解可以幫助理解每一行是如何基于前一行構建的。

楊輝三角的構建過程

初始狀態

1. 開始時，楊輝三角是空的。

第1行

2. 添加第一行，只有一個數字 1。

1

第2行

3. 第二行有兩個 1，每個都位于行的邊界。

1
1 1

第3行

4. 第三行中間的數字是上一行兩個相鄰數字之和（1 + 1）。

  11 1
1 2 1

第4行

5. 第四行，中間的兩個數字分別是上一行相鄰兩數之和（1+2 和 2+1）。

    11 11 2 11 3 3 1

第5行

6. 第五行，中間三個數字由上行相鄰數字之和得到（1+3、3+3 和 3+1）。

      11 11 2 11 3 3 11 4 6 4 1

總結過程

• 楊輝三角的每一行都從 1 開始和結束。
• 除了第一個和最后一個數字外，每個數字都是它正上方兩個數字的和。
• 第 n 行（從 1 開始計數）有 n 個數字。

解題思路與算法

方法一：逐行構建

解題步驟：

1. 初始化一個空列表 triangle 作為結果。
2. 遍歷從 0 到 numRows-1 的每一行。
3. 對于每一行，創建一個長度等于行號加一的新行，首尾元素設為1。
4. 對于每一行的中間元素，按照楊輝三角的規則，由上一行的相鄰兩個元素求和得到。
5. 將構建好的行添加到 triangle 中。

Python 代碼示例

def generate(numRows):"""生成楊輝三角的前numRows行"""triangle = []for row_num in range(numRows):row = [None for _ in range(row_num + 1)]row[0], row[-1] = 1, 1  # 第一個和最后一個元素始終為1for j in range(1, len(row) - 1):row[j] = triangle[row_num - 1][j - 1] + triangle[row_num - 1][j]triangle.append(row)return triangle

方法二：一行代碼解

解題步驟：

1. 使用列表推導式和遞推公式直接生成楊輝三角的每一行。
2. 利用 Python 的生成器語法簡化代碼實現。

Python 代碼示例

def generate(numRows):"""一行代碼生成楊輝三角"""return [[1 if j == 0 or j == i else triangle[i-1][j-1] + triangle[i-1][j] for j in range(i+1)] for i in range(numRows)]

方法三：動態規劃

解題步驟：

1. 初始化一個空列表 triangle 。
2. 從第一行到第 numRows 行，利用動態規劃的思想，每一行基于前一行生成。
3. 同樣地，每行的首尾元素為1，其他元素由上一行的兩個相鄰元素相加得到。
4. 每生成一行即存入 triangle。

Python 代碼示例

def generate(numRows):triangle = []for row_num in range(numRows):row = [1] * (row_num + 1)  # 每行元素初始化為1for j in range(1, row_num):row[j] = triangle[-1][j - 1] + triangle[-1][j]triangle.append(row)return triangle

方法四：使用遞歸

解題步驟：

1. 定義遞歸函數，如果請求行數為1，返回只包含一行的楊輝三角。
2. 否則，遞歸調用自身生成前 numRows - 1 行，然后基于最后一行計算新的一行，并添加到結果中。

Python 代碼示例

def generate(numRows):if numRows == 1:return [[1]]else:result = generate(numRows - 1)last_row = result[-1]new_row = [1]for i in range(1, len(last_row)):new_row.append(last_row[i - 1] + last_row[i])new_row.append(1)result.append(new_row)return result

方法五：迭代改進版

解題步驟：

1. 初始化一個包含第一行的列表。
2. 迭代從第二行開始，每一行都通過上一行來計算。
3. 使用臨時列表存儲當前行，計算完成后加入最終結果。

Python 代碼示例

def generate(numRows):triangle = [[1]]for row_number in range(1, numRows):prev_row = triangle[-1]current_row = [1]for j in range(1, row_number):current_row.append(prev_row[j-1] + prev_row[j])current_row.append(1)triangle.append(current_row)return triangle

算法分析

• 時間復雜度：
  • 所有方法的時間復雜度基本為 (O(n^2))，其中 (n) 是行數。每行的計算成本大約與行號成正比。
• 空間復雜度：
  • 方法一、三、四和五：(O(n^2))，需要存儲整個三角形。
  • 方法二：同樣是 (O(n^2))，但因為使用了列表推導，可能有額外的內存開銷。

不同算法的優劣勢對比

• 逐行構建（方法一）直觀易理解，適合大多數初學者。
• 一行代碼解（方法二）代碼簡潔，但可能在理解和調試時較為復雜。
• 動態規劃（方法三）標準且易于理解，展示了動態規劃思想的典型應用。
• 使用遞歸（方法四）代碼簡潔，但對于大的行數可能導致調用棧溢出。
• 迭代改進版（方法五）提供了介于方法一和方法三之間的解決方案，保持了代碼的清晰性和執行的高效性。

應用示例

楊輝三角可以用于計算組合數學中的二項式系數，這在概率論、統計學和算法設計中非常有用。例如，它可以用來計算多項式展開的系數，或者在計算概率時快速找到相關的系數。在圖形設計中，楊輝三角也被用于計算貝塞爾曲線等復雜圖形的點。