题目

题目来源：力扣（LeetCode）

给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。

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

示例 1:

输入: rowIndex = 3
输出: [1,3,3,1]

示例 2:

输入: rowIndex = 0
输出: [1]

示例 3:

输入: rowIndex = 1
输出: [1,1]

思路分析

算法实现中有两层循环，外层循环遍历的是行数，内层循环遍历的是列数。

外层循环从上往下一层一层求，复用一维数组 res (滚动数组思想)，计算每个位置上的元素，只取决于上一行的值。

内层遍历的递推公式为 res[j] = res[j] + res[j - 1]，要保证 等号 右边的 res[j] 和 res[j - 1] 是上一行的 “旧值”。

如果内层循环是从左往右，会出现 res[j - 1] 是本行的上一轮求出的新值的情况，并不是上一行的旧值。

所以，内层遍历的方向取从右往左。这样保证了计算新值时，等号右边都是旧值。

代码实现：

  1. /**
  2.  * @param {number} rowIndex
  3.  * @return {number[]}
  4.  */
  5. var getRow = function (rowIndex) {
  6.   // 第 rowIndex 行的数组长度为 rowIndex + 1
  7.   const res = new Array(rowIndex + 1);
  8.   // 每一行的第一项都确定是1
  9.   res[0] = 1;
  10.   // 从第二行开始遍历
  11.   for (let i = 1; i < rowIndex + 1; i++) {
  12.     // 第 i 行的首尾项确定是 1
  13.     res[0] = res[i] = 1;
  14.     // 从第i行的倒数第二个开始遍历到第二个   
  15.     for (let j = i - 1; j >= 1; j--) {
  16.       // 用上一行的值求出当前res[j]
  17.       res[j] = res[j] + res[j - 1];
  18.     }
  19.   }
  20.   // 返回出第 rowIndex 行的数组
  21.   return res;
  22. };

参考： https://leetcode-cn.com/problems/pascals-triangle-ii/solution/shou-hua-tu-jie-119yang-hui-san-jiao-ii-d09dc/ https://leetcode-cn.com/problems/pascals-triangle-ii/solution/gun-dong-shu-zu-de-dong-hua-tu-jie-you-h-rw5n/