每日一算 -- 斐波那契数列类型题

题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。

日常找规律

  • 当有1阶时 F(1) = 1
  • 当有2阶时 F(2) = 2(可以1阶或者2阶)
  • 当有3阶时 F(3) = 3(可以1阶或者1、2阶或者2、1)
  • 当有4阶时 F(4) = 5(可以1阶或者1、2、1、1阶或2、1、1、1或2、2、1或2、1、2)
  • 当有n阶时 F(n) = F(n - 1) + F(n - 2)
    1
    2
    3
    F(1)=1
    F(2)=2
    F(n)=F(n-1)+F(n-2)

实现方式

当我们得到推导公式,实现函数脑海里面会想到递归实现

递归

  • 时间复杂度: O(2^n)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    function fiber (n) {
    if ( n === 1) {
    return 1
    }
    if ( n === 2) {
    return 2
    }
    return fiber( n - 1) + fiber( n - 2 )
    }

循环

  • 时间复杂度: O(n)
  • 空间复杂度: O(n)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    function fiber (n) {
    let step = []
    step[0] = 1
    if ( n >= 2) {
    step[1] = 2
    }
    if ( n <= 2) {
    return n
    }
    for ( let i = 2; i <= n; i++) {
    step[i] = step[i - 1] + step[i - 2]
    }
    return step[n]
    }

循环 + 优化空间复杂度

  • 时间复杂度: O(n)
  • 空间复杂度: O(1)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    function fiber (n) {
    let prev1 = 1
    let prev2 = 2
    let result = 0
    if ( n <= 2) {
    return n
    }
    for ( let i = 2; i <= n; i++) {
    result = prev1 + prev2
    prev1 = prev2
    prev2 = result
    }
    return result
    }

总结