算法题--爬楼梯的方法数

image.png

0. 链接

题目链接

1. 题目

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

2. 思路1：动态规划

由于每一步只能爬1步或者2步, 所以假设当前已在顶端，那么如果追究倒数第二步的位置的话，只有两种可能，即

• 从n-1步处爬1步到达终点
• 从n-2步处爬2步到达终点

所以原问题就转化为两个子问题:

• 爬到第n-1步有多少种爬法
• 爬到第n-2步有多少种爬法

即

dp[n] = dp[n - 1] + dp[n - 2]

初始条件为:

dp[1] = 1
dp[2] = 2

则可以通过一次遍历O(n)复杂度求出dp[n]的值

3. 代码

# coding:utf8


class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        elif n == 2:
            return 2

        dp = [0 for _ in range(n + 1)]
        dp[1] = 1
        dp[2] = 2

        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]

        return dp[n]


solution = Solution()
print('{} => {}'.format(2, solution.climbStairs(2)))
print('{} => {}'.format(3, solution.climbStairs(3)))

输出结果

2 => 2
3 => 3

4. 结果

image.png

5. 方法2: 斐波那契数列的状态方程

image.png

6. 代码

# coding:utf8
from typing import List


class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        elif n == 2:
            return 2

        dp = [0 for _ in range(n + 1)]
        dp[1] = 1
        dp[2] = 2

        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]

        return dp[n]


class Solution1:
    def climbStairs(self, n: int) -> int:
        q = [[1, 1], [1, 0]]
        ret = self.pow(q, n)
        return ret[0][0]

    def pow(self, a: List[List[int]], n: int) -> List[List[int]]:
        # 单位矩阵
        ret = [[1, 0], [0, 1]]
        while n > 0:
            if (n & 1) == 1:
                # 只剩最后一次方了
                ret = self.multiply(ret, a)
            n >>= 1
            a = self.multiply(a, a)

        return ret

    def multiply(self, a: List[List[int]], b: List[List[int]]) -> List[List[int]]:
        # 矩阵相乘
        c = [[0] * len(b[0]) for _ in range(len(a))]
        for i in range(len(a)):
            for j in range(len(b)):
                for k in range(len(b)):
                    c[i][j] += a[i][k] * b[k][j]

        return c


def test(solution):
    import time
    time_start = time.time()
    for i in range(1000):
        solution.climbStairs(2)
        solution.climbStairs(10000)
    print('cost_time:{:.4f}秒'.format(time.time() - time_start))

solution = Solution()
print('方法1: 动态规划')
test(solution)

solution = Solution1()
print('方法2: 状态方程')
test(solution)

输出结果为

方法1: 动态规划
cost_time:6.2984秒
方法2: 状态方程
cost_time:0.6470秒

当n较大时, O(logN)复杂度相比于动态规划的O(N)复杂度，还是快很多的。