### 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](https://awjin.me/algos-js/dp/tab-memo.html)

[Tabulation vs Memoizatation](http://www.geeksforgeeks.org/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思想)

```python
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.
另外还有一个公式法：

![](/img/Algorithm/LeetCode/41512784914_.pic.jpg)

由于这里面相当于```standard Fibonacci```函数向前进了一步，排列为1，2，3，5而非原本的1，1，2，3，所以代码中使用```n+1```
```python
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.
