【动态规划】杨辉三角

给定一个非负整数 *numRows，*生成「杨辉三角」的前 numRows 行。

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

链接：https://leetcode-cn.com/problems/pascals-triangle/

定义：$dp[i][j]$​​​表示索引位置$i,j$的值

边界条件：$dp[0][0]=1，dp[1][0]=dp[1][1]=1$​​​

状态转移方程：$dp[i][j]=dp[i-1][j-1]+dp[i-1][j],i$​不为边界，边界为1

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        # dp[i][j] = dp[i-1][j]+dp[i-1][j-1]
        dp = []
        curRow = 0
        while curRow < numRows:               # 行
            if curRow==0:
                dp.append([1])
            elif curRow==1:
                dp.append([1,1])
            else:
                temp = []
                for i in range(curRow + 1):   # 列
                    if i==0 or i == curRow:   # 如果遇到了边界
                        temp.append(1)
                    else:
                        temp.append(dp[curRow-1][i]+dp[curRow-1][i-1])
                dp.append(temp)
            curRow += 1
        return dp

如果只需要序列索引为numRows（索引从0开始）的值，那么在上面代码基础上，简单改动一下即可，相关链接

class Solution:
    def getRow(self, numRows: int) -> List[int]:
        dp = []
        curRow = 0
        while curRow < numRows+1:               # 行
            if curRow==0:
                dp=[1]
            elif curRow==1:
                dp=[1,1]
            else:
                temp = []
                for i in range(curRow + 1):   # 列
                    if i==0 or i == curRow:   # 如果遇到了边界
                        temp.append(1)
                    else:
                        temp.append(dp[i]+dp[i-1])
                dp=temp
            curRow += 1
        return dp