Skip to content

Latest commit

 

History

History
131 lines (94 loc) · 3.18 KB

070._Climbing_Stairs.md

File metadata and controls

131 lines (94 loc) · 3.18 KB

70. Climbing Stairs

难度: Easy

刷题内容

原题连接

内容描述


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

解题方案

思路 1

Fibonacci 的DP版本

对于DP的不同理解造成不同的写法 Memoization will usually add on your time-complexity to your space-complexity (e.g. with tabulation you have more liberty to throw away calculations, like using tabulation with Fib lets you use O(1) space, but memoization with Fib uses O(N) stack space). 详看

Dynamic programming and memoization: bottom-up vs top-down approaches

Tabulation vs Memoizatation

  • top-down(memorize)
def memorize_fib(n): # n为第几个Fibonacci数
    memo = {1:1, 2:1}
    if n in memo:
        return memo[n]
    else:
        memo[n] = memorize_fib(n-1) + memorize_fib(n-2)
        return memo[n]

print(memorize_fib(4)) # 输出3
  • bottom up(tabulation)
def tabulation_fib(n):  # n为第几个Fibonacci数
    fib = [1, 1, 2]
    if n < 4:
        return fib[n-1]
    for k in range(3, n+1):
        fib[2] = fib[0] + fib[1]
        fib[0], fib[1] = fib[1], fib[2]
    return fib[2]

print(tabulation_fib(4)) # 输出3

这里memo用dict，用array也一样。当然用bottom up还有一点，可以只存每次最后两个数，可以save space.，这样就只用到constant space.

AC 代码(这里采用bottom up思想)

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        fib = [1, 2, 3]
        if n < 4:
            return fib[n-1]
        for k in range(3, n+1):
            fib[2] = fib[0] + fib[1]              # 永远只存3个元素，save space
            fib[0], fib[1] = fib[1], fib[2]
        return fib[2]

  • Complexity Analysis

      - Time complexity : O(n)

  - Space complexity : O(1). Constant space is used.

思路 2

另外还有一个公式法：

由于这里面相当于standard Fibonacci函数向前进了一步，排列为1，2，3，5而非原本的1，1，2，3，所以代码中使用n+1

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        import math
        sqrt5 = math.sqrt(5)
        fibn = pow((1 + sqrt5) / 2, n+1) - pow((1 - sqrt5) / 2, n+1)
        return int(float(fibn/sqrt5))

  • Complexity Analysis

      - Time complexity : O(lg(n)). pow method takes log(n) time.

  - Space complexity : O(1). Constant space is used.