LeetCode 118 杨辉三角 （Java）

杨辉三角：递归与记忆化的高效解法

问题描述

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。杨辉三角的特点是每个数等于其左上方和右上方数之和。

示例：

• 输入：numRows = 5
• 输出：[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

解法分析：递归+记忆化优化

核心思路

杨辉三角的数学定义可表示为递归关系：

f(i,j) = {
    1,                          j=0 或 j=i
    f(i-1,j-1) + f(i-1,j),     其他情况
}

直接递归会导致指数级时间复杂度（$O(2^n)$），通过二维数组存储已计算结果，可将复杂度优化至 $O(n^2)$。

算法步骤

1. 初始化结果集：创建 List<List<Integer>> 存储结果
2. 创建记忆数组：二维数组 triangle 存储计算过的值
3. 逐行生成：
   • 每行创建新数组（长度 = 行号+1）
   • 计算每个位置的值：
     • 边界位置直接设为1
     • 中间位置递归计算并存储
4. 添加到结果：将每行生成的列表加入结果集

代码实现

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>();
        int[][] triangle = new int[numRows][]; // 记忆数组
        
        for(int i = 0; i < numRows; i++) {
            triangle[i] = new int[i+1]; // 初始化当前行
            List<Integer> list = new ArrayList<>();
            
            for(int j = 0; j <= i; j++) {
                int element = element(triangle, i, j); // 获取元素值
                list.add(element);
            }
            result.add(list); // 添加当前行
        }
        return result;
    }

    // 递归计算元素值（带记忆化）
    private int element(int[][] triangle, int i, int j) {
        if(triangle[i][j] > 0) { // 已计算过
            return triangle[i][j];
        }
        
        if(j == 0 || i == j) { // 边界条件
            triangle[i][j] = 1;
            return 1;
        }
        
        // 递归计算：上左元素 + 上右元素
        triangle[i][j] = element(triangle, i-1, j-1) + element(triangle, i-1, j);
        return triangle[i][j];
    }
}

复杂度分析

• 时间复杂度：$O(n^2)$
  使用记忆化存储避免重复计算，每个元素仅计算一次
• 空间复杂度：$O(n^2)$
  存储整个杨辉三角的二维数组

迭代解法对比

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>();
        
        for(int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<>();
            for(int j = 0; j <= i; j++) {
                if(j == 0 || j == i) {
                    row.add(1); // 边界元素
                } else {
                    // 取上一行的相邻元素
                    int val = result.get(i-1).get(j-1) + result.get(i-1).get(j);
                    row.add(val);
                }
            }
            result.add(row);
        }
        return result;
    }
}

方法对比

数学特性与应用

1. 二项式系数：第n行第k个数 = $C(n,k)$
2. 对称性：$C(n,k)=C(n,n-k)$
3. 行和规律：第n行所有数之和 = $2^{n-1}$
4. 对角线性质：斜对角线数字构成斐波那契数列

实际应用场景：

• 概率计算（二项分布）
• 组合数学问题
• 代数展开系数
• 计算机图形学（曲面生成）

总结

通过记忆化优化递归解法，我们既保持了数学定义的直观性，又获得了与迭代法相当的效率。杨辉三角作为经典数学概念，其高效生成算法展示了递归优化技术的强大威力。两种解法各有优势：

• 递归+记忆化：更贴近问题数学定义
• 迭代法：实现更简洁，无递归开销

理解这两种解法的核心在于掌握递归关系的优化技巧，这对解决动态规划类问题具有重要指导意义。