0118.杨辉三角 和 0119.杨辉三角II 这两个题目都是在解决同一个问题，所以放在一起解答。
题目1
来源：0118.杨辉三角
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
难度：简单
示例1
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例2
输入: numRows = 1
输出: [[1]]
提示
1 <= numRows <= 30
分析
从示意图可以很清楚地看出杨辉三角是如何生成的。
从第三行开始，对于每一行，除去两边都是 1 外，其余元素都是他上一行相邻的元素从左到右依次相加之和。
我们已知第 1 行和第 2 行作为基本情况，对于第 n 行元素，都可以由第 n - 1 行的元素按上述规律生成，所以很明显，这是一个 动态规划 的问题。
题目要求输出前 numRows 行，我们就从第 0 行开始，按规律依次生成第 i 行，直到第 numRows - 1 行为止即可。
解答
public class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> dp = new ArrayList<>();
for (int i = 0; i < numRows; i++) {
// 生成当前第 i 行
List<Integer> row = new ArrayList<>();
for (int j = 0; j <= i; j++) {
if (j == 0 || j == i) { // 每行的左右两侧元素都是 1
row.add(1);
} else {
// 拿到上一行对应位置的元素，相加
List<Integer> prevRow = dp.get(i - 1);
row.add(prevRow.get(j - 1) + prevRow.get(j));
}
}
dp.add(row);
}
return dp;
}
}
0119.杨辉三角II 也是一道有关生成杨辉三角的题目，只不过他要求输出第 n 行的元素，而且要求 O(n) 的空间复杂度，我们来看一下。
题目2
来源：0119.杨辉三角II
给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
难度：简单
示例1
输入: rowIndex = 3
输出: [1,3,3,1]
示例2
输入: rowIndex = 0
输出: [1]
示例3
输入: rowIndex = 1
输出: [1,1]
提示
1 <= numIndex <= 33
进阶
你可以优化你的算法到 O(rowIndex) 空间复杂度吗？
分析
在做 动态规划 的题目时，很多时候要求我们输出第 n 种情况，比如斐波那契数列问题要求输出第 n 个元素。
我们一般会用一个一维或二维数组（视问题而定）来存储动态规划问题计算过程的中间结果。像这种只要求输出第 n 种情况的题目，我们可以想办法把这个存储中间结果的数组省略掉。
我们只要构造出第 n 种情况即可。解法依旧是从第 0 行开始，生成第 1 行元素，生成第 2 行元素……直到第 n 行。
解答
public class Solution {
public List<Integer> getRow(int rowIndex) {
// 最终要输出的这一行，并把他初始化
List<Integer> row = new ArrayList<>();
for (int i = 0; i <= rowIndex; i++) {
row.add(1);
}
// i 从 0 到 n，依次生成第 i 行的元素
for (int i = 0; i <= rowIndex; i++) {
// prev 用于记录上一行对应位置元素的值
int prev = row.get(0);
for (int j = 0; j <= i; j++) {
if (j == 0 || j == i) { // 每行两侧元素的值为 1
row.set(j, 1);
} else {
// 计算上一行对应位置两个元素的和
int temp = row.get(j);
row.set(j, prev + row.get(j));
prev = temp;
}
}
}
return row;
}
}
我们用了一个长度为 n 的数组（列表），所以满足 O(n) 的空间复杂度。