LeetCode(70)爬楼梯

今天是小呆刷题的第11天，今天的题目是：力扣（LeetCode)的第70题，爬楼梯

题目要求

假设你正在爬楼梯。需要n阶你才能到达楼顶。

每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

提示：

0 <= n <= 45

解题思路

第一眼看上去，这道题小呆并没有看出什么名堂，所以我们根据示例，写一下输入和输出，看看能否找出规律：

n = 1输出1，有1种方法：1
n = 2输出2，有2种方法：1 + 1, 2
n = 3输出3，有3种方法: 1 + 1 + 1, 1 + 2, 2 + 1
n = 4输出5，有5种方法：1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 2 + 1, 2 + 1 + 1， 2 + 2

观察输出，嘿，这不是跟昨天做的斐波那契数一样嘛。那就当做个复习吧~ 先写递归：

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
    if(n < 2) return n
    return fib(n - 1) + fib(n - 2)
};

再写动态规划。为了方便第一次看小呆博客的同学，还是放一张动态帮助理解，忽略动图里的0，因为本题1 <= n <= 45，所以0个台阶在本题没有意义：

动态规划-斐波那契数

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
  if(n <= 2) return n
  let dp = [1, 2]
  for(let i = 3; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]
  }
  return dp[n]
};

注意这里跟第509题还是有一丢丢的细微区别，因为本题不存在0个台阶，所以dp[0],dp[1]的值是1,2。其次for循环的初始值是3，注意不要粗心哟。就这样今天的算法还没开始就结束了，小呆有点不甘心，所以上述代码有没有可以优化的项呢？答案是有的。

我们用dp数组维护了一个从1-n的数据，但其实我们每次计算只需要2个数n - 1, n - 2，那能不能不用数组，只维护2个变量数据就可以了呢，每次循环的时候，我们去更新它。

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
  if(n <= 2) return n
  let early = 1, prev = 2
  for(let i = 3; i <= n; i++) {
    let temp = prev
    prev = prev + early
    early = temp
  }
  return prev
}

小结

算法不只有一种解法，即使已经做出来的解法，也许还有优化的空间。很多同学在刷算法题的时候，太执着于一题多解，这在前期其实会浪费很多时间。初期刷算法题，小呆自己的思路是不纠结学会多种解法，先掌握一种，然后尽量先挑简单的题型，多做。去分析和归类，等大部分题都刷过一遍之后，会的那种解法已经孰能生巧，举一反三之后，再去看更多的解法。加油吧~