LeetCode-118. 杨辉三角 - sheep44044的小站

动态规划#

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

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

示例 1:

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

示例 2:

1
输入: numRows = 1
2
输出: [[1]]

思路(手撕)

与 70. 爬楼梯 类似

1
func generate(numRows int) [][]int {
2
    if numRows == 1 {
3
        return [][]int{{1}}
4
    }
5

6
    if numRows == 2 {
7
        return [][]int{{1},{1, 1}}
8
    }
9

10
    res := [][]int{{1}, {1, 1}}
11
    for i := 2; i < numRows; i++ {
12
        path := make([]int, i+1)
13
        path[0], path[len(path)-1] = 1, 1
14
        for j := 1; j < i; j++ {
15
            path[j] = res[i-1][j-1] + res[i-1][j]
16
        }
17
        res = append(res, path)
18
    }
19
    return res
20
}