图解精选 TOP 面试题 007 | 杨辉三角

江不知

发布于 2020-01-02 07:53:47

42500

代码可运行

文章被收录于专栏：编程拯救世界编程拯救世界

运行总次数：0

代码可运行

该系列题目取自 LeetCode 精选 TOP 面试题列表：https://leetcode-cn.com/problemset/top/

题目描述

LeetCode 118. 杨辉三角：https://leetcode-cn.com/problems/pascals-triangle/

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

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

示例:

输入: 5

输出:

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

解题思路

杨辉三角可以说是一道大家非常熟悉的题目了，一开始学 C 语言的时候就经常做打印杨辉三角的作业。

杨辉三角的特征是：每个数是它左上方和右上方的数的和。

但是，由于我们使用的数组都是规整的矩形，不是三角形，没有所谓「左上方」、「右上方」的说法。为了方便观察，我们将每行的数字左对齐：

杨辉三角左对齐

这样一来，我们很容易观察到：

杨辉三角每一行的第一位和最后一位都为 1
中间位置的数字是由它上一行对应位置的数字以及上一行对应位置左侧的数字相加得到

因为下一行的情况总需要由上一行的情况推出，即我们需要记录每一行的结果。所以构建杨辉三角本质上是一个动态规划问题，我们可以总结出如下推导式：

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

其中，dp[i][j] 表示第 i 行的第 j 个数。

具体实现

Python

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        res = []

        for i in range(numRows):
            tmp = []
            for j in range(i + 1):
                # 首项和末项都是 1
                if j == 0 or j == i:
                    tmp.append(1)
                else:
                    tmp.append(res[i - 1][j - 1] + res[i - 1][j])
            res.append(tmp)

        return res

Go

func generate(numRows int) [][]int {
    var res [][]int = make([][]int, numRows)

    for i := 0; i < numRows; i++ {
        res[i] = make([]int, i + 1)
        for j := 0; j < i + 1; j++ {
            if j == 0 || j == i {
                res[i][j] = 1
            } else {
                res[i][j] = res[i - 1][j - 1] + res[i - 1][j]
            }
        }
    }

    return res
}