LeetCode(118)杨辉三角

今天是小呆刷题的第 17 天，今天的题目是：力扣（LeetCode)的第 118 题，杨辉三角

题目要求

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

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

杨辉三角

示例：

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

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

提示：

1 <= numRows <= 30

解题思路

这道题其实官方已经给了非常容易理解的规律和图示：每个数是它左上方和右上方的数的和。

我们可以用一个二维数组来描述示例 1 的数据：

1	`let list = [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]`

根据上面给出的规律能够得出, 首尾的数字一定是 1, 其次从第三行开始，除去首尾，其他的数字都是它左上方和右上方的数的和，所以我们可以做出以下公式：（用i表示行，用j表示列）

list[i][0] = 1 每行的第一个数字是 1
list[i][j] = list[i - 1][j - 1] + list[i - 1][j] 当前行的第j个数等于上一行的j - 1 + 上一行的j
list[i][i] = 1 每行的最后一个数字是 1

不难看出，这道题其实用动态规划就可以解决:（本题动态 gif 图直接看上面给的官方图即可）

/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function (numRows) {
  let ans = []
  for (let i = 0; i < numRows; i++) {
    ans[i] = [1] // 每一行的第一个数都是1
    for (let j = 1; j < i; j++) {
      ans[i][j] = ans[i - 1][j - 1] + ans[i - 1][j] // 当前行的第j个数等于上一行的j - 1 + 上一行的j
    }
    ans[i][i] = 1 // 每一行的最后一个数都是1
  }
  return ans
}