70

题目

方法一：递归该方法超时啦

var climbStairs = function(n) {
  if(n==1)return n;
  if(n==2)return n;
  return climbStairs(n-1) + climbStairs(n-2);
};

方法二：记忆递归使用一个数组来保存递归过的值。

var climbStairs = function(n) {
  let arr = new Array(n).fill(0);
  function ans(n){
    if(arr[n]>0)return arr[n];
    if(n==1)return n;
    if(n==2)return n;
    arr[n] = ans(n-1) + ans(n-2);
    return arr[n];
  }
  return ans(n);
};

方法三：动态规划

var climbStairs = function(n) {
  if(n<=2)return n;
  let arr = [1,2];
  for(let i=3;i<=n;i++){
    let temp = arr[0]+arr[1];
    [arr[0],arr[1]] = [arr[1],temp];
  }
  return arr[1];
};