难度: Easy
给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1:
输入: rowIndex = 3 输出: [1,3,3,1]
示例 2:
输入: rowIndex = 0 输出: [1]
示例 3:
输入: rowIndex = 1 输出: [1,1]
提示:
0 <= rowIndex <= 33
进阶：
你可以优化你的算法到 O(rowIndex) 空间复杂度吗？
Submission
运行时间: 19 ms
内存: 16.1 MB
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
ans = []
preList = []
for i in range(rowIndex + 1):
subList = []
for j in range(i + 1):
if j == 0 or j == i:
subList.append(1)
else:
subList.append(preList[j - 1] + preList[j])
ans = subList
preList = subList
return ans
Explain
该题解采用动态规划的思路。通过观察杨辉三角的特点，可以发现每一行的数字都可以由上一行的数字计算得到。第 i 行的第 j 个数等于第 i-1 行的第 j-1 个数和第 j 个数之和。因此，可以通过迭代的方式，从第 0 行开始，逐行计算杨辉三角的每个数字，直到计算出第 rowIndex 行的数字。
时间复杂度: O(rowIndex^2)
空间复杂度: O(rowIndex)
```python
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
ans = [] # 存储当前行的数字
preList = [] # 存储上一行的数字
for i in range(rowIndex + 1): # 迭代计算每一行
subList = []
for j in range(i + 1): # 计算当前行的每个数字
if j == 0 or j == i:
subList.append(1) # 首尾数字为 1
else:
subList.append(preList[j - 1] + preList[j]) # 中间数字由上一行的相邻两个数字相加得到
ans = subList
preList = subList
return ans
```
Explore
在该实现中，使用`if j == 0 or j == i`来处理每行的首尾元素是安全的，因为这种情况确确实实只会在每行的开始和结束发生。`j == 0`总是成立于行的开始，`j == i`总是成立于行的结束。这种处理方式明确地确保了每行的开始与结束元素始终是1，这与杨辉三角的定义相符。因此，不会存在边界错误，如遗漏或重复赋值的情况。
当前算法的时间复杂度和空间复杂度均为O(n^2)，其中n为`rowIndex`。对于`rowIndex`的最大值33，这意味着最坏情况下将处理不超过1122个元素，这对现代计算机来说是可接受的。然而，如果需要处理更大的`rowIndex`或追求更高的效率，可以考虑使用滚动数组技术来减少空间复杂度到O(n)，或者使用组合数学公式直接计算每个位置的值而不通过迭代整个三角形，从而提高效率。
直接从第`rowIndex`行开始构建杨辉三角的方法在理论上是不可行的，因为每一行的元素都是基于上一行元素的值计算得到的。没有先构建上一行，就无法计算当前行。因此，即使我们只需要第`rowIndex`行的数据，我们仍然需要从第0行开始逐行构建，直到达到所需的行。另一种可能性是使用组合数学中的二项式系数直接计算第`rowIndex`行的每一个元素，这种方法可以不通过构建整个三角形来直接获取任何指定行，但需要一定的数学背景来实现。