119. 杨辉三角 II

题目

给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。

进阶：

你可以优化你的算法到 O(k) 空间复杂度吗？

题解

递推

var getRow = function(rowIndex) {
  const row = new Array(rowIndex + 1).fill(0);
  row[0] = 1;
  for (let i = 1; i <= rowIndex; ++i) {
    for (let j = i; j > 0; --j) {
      row[j] += row[j - 1];
    }
  }
  return row;
};

时间复杂度：O(rowIndex^2)。 空间复杂度：O(1)。不考虑返回值的空间占用。

线性递推

var getRow = function(rowIndex) {
  const row = new Array(rowIndex + 1).fill(0);
  row[0] = 1;
  for (let i = 1; i <= rowIndex; ++i) {
    row[i] = (row[i - 1] * (rowIndex - i + 1)) / i;
  }
  return row;
};

时间复杂度：O(rowIndex)。 空间复杂度：O(1)。不考虑返回值的空间占用。