动态规划-爬楼梯(leetcode70)

分析：假设现在只有一个台阶，那么显然只有一种方法跳到楼顶，如果现在有两个台阶我可以选择每次只跳一个台阶，也可以选择一次性跳两个台阶，如果现在有三个台阶的话可以一阶一阶的跳，也可以先跳一阶再跳两阶，也可以先跳两阶再跳一阶，现在我们仔细想一下，我到第三阶的情况无外呼就是两种，要么从前面的第二阶跳一下上来，要么从前面的前面跳两阶上来，所以到第三阶的可能性不就是到前面那一阶的可能性，加上前面的前面那一阶的可能性，我们设置一个数组用于保存之前台阶可能性，不就能递推出后面我们要计算的可能性了吗？

/**
 * @param {number}
 * @return {number}
 */
var climbStairs = function(n) {
  if(n < 3) return n
  let dp = [] // 保存之前阶梯可能的次数
  dp[0] = 1
  dp[1] = 2
  for(let i= 2;i<n;i++){
    dp[i] = dp[i-1] + dp[i-2]
  }
  return dp[n-1]
};

我们只用在使用数组时起时只用到了最后两个状态，之前的状态根本就没用到，可以用两个变量保存起来，实现滑动数组的效果。

var climbStairs2 = function(n) {
  if(n < 3) return n
  let first = 1,second=2;
  for(let i= 2;i<n;i++){
    let temp = second;
    second = first + second;
    first = temp
  }
  return second
}