070._Climbing_Stairs.md

70. Climbing Stairs

题目: https://leetcode.com/problems/climbing-stairs/

难度: Easy

思路：

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.
  

另外还有一个公式法：

由于这里面相当于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.