【算法】杨辉三角-动态规划

题目

原题地址：118. 杨辉三角 - 力扣（LeetCode）

解题思路

fn(n) 的返回值是一个有 n 个元素的数组，根据杨辉三角的特性，fn(n)[1] = fn(n - 1)[0] + fn(n - 1)[1]。

• 递归实现

function generate(numRows) {
  const cache = [null, [1]];
  function generateArr(numRows) {
    if (cache[numRows]) {
      return cache[numRows];
    }
    const arr = generateArr(numRows - 1);
    const newArr = new Array(numRows);
    for (let i = 0; i < numRows; i++) {
      newArr[i] = (arr[i - 1] || 0) + (arr[i] || 0);
    }
    cache[numRows] = newArr;
    return cache[numRows];
  }

  generateArr(numRows);
  cache.shift();

  return cache;
}

时间复杂度：$T(n) * T(n) = O(n^2)$

空间复杂度：$O(1)$

• 迭代实现

/**
 * @param {number} numRows
 * @return {number[][]}
 */
var generate = function (numRows) {
  if (numRows === 1) {
    return [[1]];
  }

  if (numRows === 2) {
    return [[1], [1, 1]];
  }

  const ans = [[1], [1, 1]];
  for (let i = 2; i < numRows; i++) {
    const row = new Array(i + 1).fill(1);
    for (let j = 1; j < i; j++) {
      row[j] = ans[i - 1][j - 1] + ans[i - 1][j];
    }
    ans.push(row);
  }

  return ans;
};

时间复杂度：$O(n^2)$

空间复杂度：$O(1)$