动态规划 - 台阶问题

问题

有一座高度是10级台阶的楼梯，从下往上走，每跨一步只能向上1级或者2级台阶。要求用程序来求出一共有多少种走法

方案

递归

function getResultByRecursion(n){
  if (n < 1) {
    return 0;
  }
  if (n == 1) {
    return 1;
  }
  if (n == 2) {
    return 2;
  }
  return getResultByRecursion(n - 1) + getResultByRecursion(n - 2);
}

console.log(getResultByRecursion(10)) //89

时间复杂度为2的n次方

备忘录算法

let catchData = {}; //缓存已经计算过的步法

function getResultByMap(n){
  if (n < 1) {
    return 0;
  }
  if (n == 1) {
    return 1;
  }
  if (n == 2) {
    return 2;
  }
  if (catchData[n]) {
    return catchData[n];
  } else {
    const value = getResultByMap(n - 1) + getResultByMap(n - 2);
    catchData[n] = value;
    return value;
  }
}

console.log(getResultByMap(10)) //89

时间复杂度和空间复杂度都为O(n)

动态规划 （从底向上）

function getResultByDP(n){
  if (n < 1) {
    return 0;
  }
  if (n == 1) {
    return 1;
  }
  if (n == 2) {
    return 2;
  }

  let a = 1;
  let b = 2;
  let temp = 0;

  for (let i = 3; i < n + 1 ; i++) {
    temp = a + b;
    a = b;
    b = temp;
  }
  return temp;
}

console.log(getResultByDP(10)) //89

时间复杂度为O(n)，空间复杂度为O(l)