30杨辉三角II

给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。

在杨辉三角中，每个数是它左上方和右上方的数的和。

示例:
输入: 3
输出: [1,3,3,1]

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        # j行的数据, 应该由j - 1行的数据计算出来.
        # 假设j - 1行为[1,3,3,1], 那么我们前面插入一个0(j行的数据会比j-1行多一个),
        # 然后执行相加[0+1,1+3,3+3,3+1,1] = [1,4,6,4,1], 最后一个1保留即可.
        r = [1]
        for i in range(1, rowIndex + 1):
            r.insert(0, 0)
            # 因为i行的数据长度为i+1, 所以j+1不会越界, 并且最后一个1不会被修改.
            for j in range(i):
                r[j] = r[j] + r[j + 1]
        return r

模拟法（动态规划）
1,特判，若k==0k==0，返回[1][1]
2,初始化dp=[1,1]dp=[1,1]，表示第二行
3,遍历区间[3,k+2)[3,k+2)，表示从第三行开始遍历：
初始化cur=[1,0,...,0,1]cur=[1,0,...,0,1]，长度为当前行数,从curcur第二个元素到倒数第二个元素，利用动态规划：cur[j]=dp[j-1]+dp[j]cur[j]=dp[j−1]+dp[j],将dpdp更新为curcur

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        if(rowIndex==0):
            return [1]
        dp=[1,1]
        for i in range(3,rowIndex+2):
            cur=[0]*(i)
            cur[0]=cur[-1]=1
            for j in range(1,i-1):
                cur[j]=dp[j-1]+dp[j]
            dp=cur
        return dp

来源：力扣（LeetCode）