楊輝三角（Pascal Triangle）Java 實現：二維陣列構建與規律解析

楊輝三角數學規律

楊輝三角（帕斯卡三角）是二項式係數的幾何排列。第 n 行（從 0 計數）包含 n+1 個數，對應 (a+b)^n 展開係數。

核心遞推公式：

• 邊界：首列（j=0）與對角線（j=i）恆為 1。
• 內部：C(i, j) = C(i-1, j-1) + C(i-1, j)，即「左上 + 正上」。

Java 實現：8 行完整三角

public class YangHuiTriangle {
    public static void main(String[] args) {
        final int ROWS = 8;
        int[][] triangle = new int[ROWS][ROWS]; // 方陣預分配，下三角有效

        // 填充下三角區
        for (int i = 0; i < ROWS; i++) {
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    triangle[i][j] = 1; // 邊界條件
                } else {
                    triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]; // 遞推
                }
            }
        }

        // 左對齊列印
        for (int i = 0; i < ROWS; i++) {
            for (int j = 0; j <= i; j++) {
                System.out.printf("%-4d", triangle[i][j]);
            }
            System.out.println();
        }
    }
}

輸出結果

1
1   1
1   2   1
1   3   3   1
1   4   6   4   1
1   5   10  10  5   1
1   6   15  20  15  6   1
1   7   21  35  35  21  7   1

進階優化與變體

1. 空間優化：單一陣列滾動更新

利用 C(n,k) = C(n,k-1) * (n-k+1) / k 逐行計算，僅需 O(n) 空間。

int[] row = new int[ROWS];
for (int i = 0; i < ROWS; i++) {
    row[i] = 1; // 對角線
    for (int j = i - 1; j > 0; j--) // 逆序避免覆蓋前值
        row[j] = row[j] + row[j-1];
    // 列印 row[0..i]
}

2. 直角楊輝三角（左對齊矩陣）

若需矩陣形式（如圖片所示），直接用 triangle[i][j] 存儲，列印時補空格對齊。

3. 大數支援：BigInteger

超過 34 行後 int 溢位，改用 BigInteger[][] 或 List<BigInteger>。

經典面試延伸題

1. 求第 n 行第 k 個數：直接用組合公式 C(n,k)，避免構建整個三角，時間 O(k)、空間 O(1)。
2. 三角形總和：第 n 行和為 2^n。
3. 質數行特徵：若 n 為質數，第 n 行除首尾外皆為 n 的倍數。
4. 斐波那契數列：對角線求和即得 Fibonacci 數列。

教學重點總結

• 二維陣列下三角填充模式：for (j=0; j<=i; j++)
• 邊界條件優先判斷（j==0 || j==i），避免陣列越界。
• 遞推關係 dp[i][j] = dp[i-1][j-1] + dp[i-1][j] 是動態規劃入門典範。
• 格式化輸出 printf("%-4d") 讓對齊更美觀。