每日算法 — 使用java实现杨辉三角：动态规划与组合数公式

一、问题引入

杨辉三角（Pascal’s Triangle）是组合数学中最经典的几何排列之一。它的每一行对应二项式展开的系数，从顶端开始，每个数等于上方两数之和。对于算法学习者来说，杨辉三角是理解动态规划递推思想的绝佳入门案例。

本文将用Java实现两种生成杨辉三角的方法：动态规划递推法和组合数公式直接计算法，并对比它们的时空复杂度。

二、算法原理

2.1 动态规划递推法

杨辉三角的核心递推关系非常简单：
– 第0行只有1
– 每行的首尾元素都是1
– 中间元素 C(i,j) = C(i-1,j-1) + C(i-1,j)

这个递推式天然符合动态规划的定义：当前状态由之前的状态推导而来。

2.2 组合数公式法

根据组合数学定义，杨辉三角第i行第j列的元素可以直接用组合数公式计算：

C(i,j) = i! / (j! * (i-j)!)

为了避免阶乘溢出，可以采用递推计算组合数：

C(i,j) = C(i,j-1) * (i-j+1) / j

三、Java代码实现

import java.util.ArrayList;
import java.util.List;

/**
 * 杨辉三角生成器
 * 包含动态规划递推法和组合数公式法两种实现
 */
public class PascalTriangle {

    /**
     * 方法1：动态规划递推法
     * 时间复杂度：O(numRows^2)
     * 空间复杂度：O(numRows^2)（存储结果）
     *
     * @param numRows 要生成的行数
     * @return 杨辉三角的二维列表
     */
    public List<List<Integer>> generateByDP(int numRows) {
        List<List<Integer>> result = new ArrayList<>();

        if (numRows <= 0) {
            return result;
        }

        // 第0行总是[1]
        List<Integer> firstRow = new ArrayList<>();
        firstRow.add(1);
        result.add(firstRow);

        // 从第1行开始递推
        for (int i = 1; i < numRows; i++) {
            List<Integer> prevRow = result.get(i - 1);
            List<Integer> currentRow = new ArrayList<>();

            // 每行第一个元素是1
            currentRow.add(1);

            // 中间元素 = 上一行左上方 + 上一行正上方
            for (int j = 1; j < i; j++) {
                int val = prevRow.get(j - 1) + prevRow.get(j);
                currentRow.add(val);
            }

            // 每行最后一个元素是1
            currentRow.add(1);

            result.add(currentRow);
        }

        return result;
    }

    /**
     * 方法2：组合数公式法（递推计算避免阶乘溢出）
     * 时间复杂度：O(numRows^2)
     * 空间复杂度：O(numRows^2)
     *
     * @param numRows 要生成的行数
     * @return 杨辉三角的二维列表
     */
    public List<List<Integer>> generateByCombination(int numRows) {
        List<List<Integer>> result = new ArrayList<>();

        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<>();
            long combination = 1; // 使用long防止中间计算溢出

            for (int j = 0; j <= i; j++) {
                if (j == 0) {
                    combination = 1;
                } else {
                    // C(i,j) = C(i,j-1) * (i-j+1) / j
                    combination = combination * (i - j + 1) / j;
                }
                row.add((int) combination);
            }

            result.add(row);
        }

        return result;
    }

    /**
     * 获取杨辉三角中指定位置的值（空间优化版）
     * 只使用O(numRows)额外空间生成最后一行
     *
     * @param rowIndex 行索引（从0开始）
     * @return 该行的列表
     */
    public List<Integer> getRow(int rowIndex) {
        List<Integer> row = new ArrayList<>();

        // 利用组合数递推公式，从后往前更新，避免覆盖
        for (int i = 0; i <= rowIndex; i++) {
            row.add(1); // 先扩展列表
            // 从倒数第二个元素开始更新
            for (int j = i - 1; j > 0; j--) {
                row.set(j, row.get(j) + row.get(j - 1));
            }
        }

        return row;
    }

    /**
     * 打印杨辉三角（格式化对齐）
     */
    public void printTriangle(List<List<Integer>> triangle) {
        int n = triangle.size();
        int maxVal = triangle.get(n - 1).get(n / 2);
        int maxWidth = String.valueOf(maxVal).length();
        int rowWidth = (n * 2 - 1) * maxWidth;

        for (int i = 0; i < n; i++) {
            List<Integer> row = triangle.get(i);
            int spaces = (rowWidth - row.size() * maxWidth) / 2;

            // 打印前导空格
            for (int s = 0; s < spaces; s++) {
                System.out.print(" ");
            }

            for (int val : row) {
                System.out.printf("%" + maxWidth + "d ", val);
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        PascalTriangle solution = new PascalTriangle();
        int numRows = 10;

        System.out.println("=== 动态规划递推法 ===");
        List<List<Integer>> dpResult = solution.generateByDP(numRows);
        solution.printTriangle(dpResult);

        System.out.println("\n=== 组合数公式法 ===");
        List<List<Integer>> combResult = solution.generateByCombination(numRows);
        solution.printTriangle(combResult);

        System.out.println("\n=== 空间优化获取第" + numRows + "行 ===");
        List<Integer> row = solution.getRow(numRows - 1);
        System.out.println(row);
    }
}

四、复杂度分析

五、算法应用

杨辉三角不仅是数学上的优美结构，在算法中也有广泛应用：
– 组合数查询：杨辉三角的第n行第k个数即为C(n,k)
– 概率计算：二项分布的概率质量函数直接使用组合数
– 路径计数：网格中从起点到终点的路径数问题

六、总结

杨辉三角虽然看似简单，但它涵盖了动态规划的核心思想：状态定义 + 状态转移方程。通过两种实现方式的对比，读者可以体会到递推与数学公式之间的等价关系，以及空间优化的技巧。这是学习更复杂动态规划问题的理想起点。