优化动态规划的空间复杂度

Demo

斐波那契算法

// 常规方法
function fibonacci(n) {
  if (n === 1 || n === 2) {
    return 1;
  }
  const dp = [1, 1];
  for (let i = 2; i < n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];
  }
  return dp[n - 1];
}

// 优化方案
function fibonacci(n) {
  if (n === 1 || n === 2) {
    return 1;
  }
  let p1 = 1;
  let p2 = 1;
  let r;

  for (let i = 2; i < n; i++) {
    r = p1 + p2
    p1 = p2;
    p2 = r;
  }
  return r;
}

方格有多少路径

// 常规方法
var uniquePaths = function(m, n) {
  const dp = new Array(n).fill(1);
  for (let i = 1; i < m; i ++) {
    for (let j = 1; j < n; j ++) {
      dp[j] += dp[j - 1]
    }
  }

  return dp[n - 1];
}