Leetcode--118、杨辉三角

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

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

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

解题思路一：

典型的动态规划问题：每一行的首尾都是1，除去首尾之外每一个当前元素等于上一行当前列元素与上一行当前列前一列元素之和，则初始化dp（默认元素都为1），动态规划方程为：

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

代码实现：

def generate(num):
    res = []
    for i in range(num):
        res.append([0] * (i + 1))
    for i in range(num):
        for j in range(len(res[i])):
            if j == 0 or j == i:
                res[i][j] = 1
            else:
                res[i][j] = res[i - 1][j] + res[i - 1][j - 1]
    return res


print(generate(5))

输出：

解题思路二：

思路与上述方法相同，只不过简化了部分内容

代码实现：

def generate(num):
    dp = [[1]]
    for i in range(1, num):
        dp.append(dp[-1] + [1])
        for j in range(1, len(dp[-1]) - 1):
            dp[-1][j] = dp[-2][j] + dp[-2][j - 1]
    return dp


print(generate(5))

输出：

解题思路三：

属于一个取巧解法，我们可以观察到当前行元素等于上一行元素与其自身错一位相加得到的。如图：

代码实现：

def generate(num):
    if num == 0:
        return []
    res = [[1]]
    while len(res) < num:
        newRow = [a+b for a, b in zip(res[-1] + [0], [0] + res[-1])]
        res.append(newRow)
    return res


print(generate(5))

输出：

关于zip函数的用法举例：