当前位置：首页 > news >正文

杨辉三角（二维数组自底向上DP表格法详解·新手友好版）

news 2026/5/26 9:19:54

作为动态规划入门从一维DP过渡到二维DP的核心经典题型，杨辉三角是爬楼梯问题的最佳进阶练习。相比于抽象的嵌套集合DP写法，二维数组DP表格法逻辑更直观、表格可视化更强，完美适配新手理解二维DP的推导逻辑。

本文将基于二维数组存储DP表格的写法，沿用动态规划标准解题框架，从题目解析、DP思路拆解、逐行推导、完整代码实现、易错点总结全方位讲解，带你彻底吃透二维DP基础逻辑，为后续二维DP、路径类DP题目铺垫核心思路。

一、题目回顾

题目描述：给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。杨辉三角核心规则：每行首尾元素固定为1，中间每个元素等于上一行相邻两个元素之和。

示例：

输入：numRows = 5

输出：

[ [1], [1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1] ]

核心解题要求：采用二维数组自底向上DP表格法解题，用数组存储完整DP状态，直观理解二维DP的状态存储与推导逻辑，拒绝死记硬背公式。

二、动态规划核心思想（二维DP专属）

动态规划的核心始终是：化繁为简、记录子问题解、自底向上推导。

爬楼梯是一维DP，只用单个数组记录每阶台阶的结果；而杨辉三角是标准二维DP问题，存在「行、列」两个维度的状态，因此需要用二维数组作为DP表格，存储每一行、每一列的数值。

自底向上核心思路：先初始化最基础的边界值（每行首尾1），再从第三行开始，利用上一行已计算好的子问题结果，逐行、逐列推导当前位置的值，最终得到完整的杨辉三角。

三、杨辉三角DP完整拆解（二维数组版）

1. 定义DP数组（核心）

我们定义二维数组作为DP状态表，专门存储杨辉三角所有位置的数值：

dp[i][j] 含义：代表杨辉三角中，第 i 行、第 j 列的元素值。

为了完整存储 numRows 行数据，我们初始化二维数组：int[][] arr = new int[numRows][numRows]，该数组就是我们的核心DP表格。

2. 推导递推公式（核心逻辑）

分析杨辉三角数值规律：

任意一个非边界位置的元素，都由「上一行正上方元素」和「上一行左上方元素」相加得到。

对应DP递推公式：

arr[i][j] = arr[i-1][j] + arr[i-1][j-1]

3. 初始化边界条件（DP起点）

递推公式无法计算首尾元素，这是DP问题的基础子问题，也是固定边界：

每行第一个元素：j == 0，值固定为 1
每行最后一个元素：i == j，值固定为 1

所有二维DP的推导，都基于这组边界条件自底向上展开。

4. 自底向上表格填充过程（实例演示）

以 numRows = 5 为例，一步步填充二维DP数组：

第0行(i=0)：j=0，触发边界 → arr[0][0] = 1 → [1]

第1行(i=1)：j=0、j=1 触发边界 → arr[1][0]=1，arr[1][1]=1 → [1,1]

第2行(i=2)：

j=0、j=2 为边界=1；j=1 套用公式 arr[1][1]+arr[1][0]=2 → [1,2,1]

第3行(i=3)：

首尾为1；j=1=arr[2][1]+arr[2][0]=3，j=2=arr[2][2]+arr[2][1]=3 → [1,3,3,1]

第4行(i=4)：

首尾为1；j=1=4、j=2=6、j=3=4 → [1,4,6,4,1]

填充完成后，将二维DP数组的有效数值转为集合，即为最终答案。

四、完整代码实现（你的二维数组DP原版、超详细注释）

以下为纯原版你的写法，保留二维数组DP核心逻辑，新增新手专属注释，完全贴合上述DP思路：

import java.util.ArrayList; import java.util.List; class Solution { public List<List<Integer>> generate(int numRows) { // 最终结果集合 List<List<Integer>> res = new ArrayList(); // 核心：二维数组DP表格，存储所有DP状态值 int[][] arr = new int[numRows][numRows]; // 自底向上遍历每一行 for(int i = 0; i < numRows; i++){ // 存储当前行的结果 List<Integer> row = new ArrayList(); // 遍历当前行的每一列（第i行有i+1个元素） for(int j = 0; j <= i; j++){ // DP边界条件：每行首尾元素为1 if(i == j || j == 0){ arr[i][j] = 1; }else{ // DP递推公式：当前值 = 上一行两个相邻值之和 arr[i][j] = arr[i-1][j] + arr[i-1][j-1]; } // 将DP表格的值存入当前行 row.add(arr[i][j]); } // 将当前行加入最终结果 res.add(row); } return res; } }