Leetcode解题-Climbing Stairs

发表于   |   分类于   |  

描述

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?

分析

稍一分析就知道答案是斐波那契数F(n + 1)。因为f(1) = 1, f(2) = 2，而n > 2时，有多少种走法呢，可以分解为：

  1. 如果第一次走一步，那么有f(n-1)种走法。
  2. 如果第一次走两步，那么有f(n-2)种走法。
  3. 因此f(n) = f(n-1) + f(n-2)，故f(n)是第n+1个斐波那契数。

使用动态规划算法，时间复杂度O(n)，空间复杂度O(1)。

代码

Python

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 2:
            return n
        a, b = 1, 2
        for i in xrange(n - 2):
            a, b = b, a + b
        return b

热评文章