【算法积累】动态规划与斐波那契数列

2019-12-21

题目

  注：本题来自LeetCode题库70.爬楼梯。

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

  示例1： 

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

  示例2：

1
2
3
4
5
6
 输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

解法1：动态规划法

  不难发现，这个问题可以被分解为一些包含最优子结构的子问题，即它的最优解可以从其子问题的最优解来有效地构建，我们可以使用动态规划来解决这一问题。
  假设我们要爬到第n个台阶，则有两种情况：一是爬到第(n-1)个台阶，然后再往上爬1个台阶即可；二是爬到第(n-2)个台阶，然后再往上爬2个台阶即可。也就是说，爬到第n个台阶的方法数，就是爬到第(n-1)个台阶的方法数与爬到第(n-2)个台阶的方法数之和。
  特别地，当n=1时，方法数为1；当n=2时，方法数为2（即1+1或直接爬2个台阶）。
  代码实现如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 语言：C
// 执行用时：0ms（又是0ms，具体情况未知）
// 内存消耗：6.8MB
int climbStairs(int n){
    if (n == 1)
        return 1;
    int first, second, third, i;
    first = 1;
    second = 2;
    for (i = 3; i < n + 1; i++)
    {
        third = first + second;
        first = second;
        second = third;
    }
    return second;
}

  这种解法的时间复杂度为O(n)，空间复杂度为O(n)。

解法2：斐波那契数列法

  我们再分析一下解法1，不难发现这其实就是斐波那契数列。所以这道题还可以用斐波那契数列法来解决。下面给出C和Python 3的代码： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 语言：C
// 执行用时：0ms（我不想再说什么了……为啥又是0啊QAQ……）
// 内存消耗：6.9MB
int climbStairs(int n){
    if (n == 1)
        return 1;
    int fib[100];
    fib[1] = 1;
    fib[2] = 2;
    int i;
    for (i = 3; i <= n; i++)
        fib[i] = fib[i - 1] + fib[i - 2];
    return fib[n];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
"""
语言：Python 3
执行用时：36ms（诶它终于不是0ms了嘿嘿QvQ）
内存消耗：12.7MB
"""
class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        fib = [1, 1, 2]
        for i in range(3, n + 1):
            next = fib[i - 1] + fib[i - 2]
            fib.append(next)
        return fib[n]

  同样地，这种解法的时间复杂度为O(n)，空间复杂度为O(n)。

解法3：斐波那契公式法

  既然知道这道题本质上就是斐波那契数列了，那么我们就可以直接使用公式啦！
  斐波那契数列的公式如下：
$$F_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\right)$$
  套用这个公式可以很快地解决本题。Python 3代码如下： 

1
2
3
4
5
6
7
8
9
10
"""
语言：Python 3
执行用时：48ms（比上一个方法慢了不少诶QnQ）
内存消耗：12.8MB
"""
import math

class Solution:
    def climbStairs(self, n: int) -> int:
        return int((pow((1+math.sqrt(5))/2, n+1) - pow((1-math.sqrt(5))/2, n+1)) / math.sqrt(5))

  这种方法的时间复杂度为O(log(n))（pow()将会用去log(n)的时间），空间复杂度为O(1)（使用常量级空间）。