广东商城网站建设线上推广产品

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

问题描述

给定一个非负整数 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=if(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;}
}

方法对比

方法	时间复杂度	空间复杂度	优势
递归+记忆化	$O(n^2)$	$O(n^2)$	直接体现数学定义
迭代	$O(n^2)$	$O(n^2)$	代码更简洁，无递归开销

数学特性与应用

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

实际应用场景：

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

总结

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

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

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