leetcode-70 爬樓梯

假設你正在爬樓梯。需要 n 步你才能到達樓頂。

每次你可以爬 1 或 2 個台階。你有多少種不同的方法可以爬到樓頂呢？

注意：給定 n 是一個正整數。

示例 1：
輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂。
1.  1 步 + 1 步
2.  2 步

示例 2：

輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂。
1.  1 步 + 1 步 + 1 步
2.  1 步 + 2 步
3.  2 步 + 1 步
           

思路：

假設f(n)為在第n階台階的情況下，所有不同的跳法方法的總和！
1.如果在n-1階下跳一格，那麼有 f(n-1) 種跳法；
2.如果在n-2階下跳兩格，那麼有 f(n-2) 種跳法；
是以f(n) = f(n-1) + f(n-2)，實際結果即為斐波納契數。
           

代碼：

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 0: return 1
        if n == 1: return 1
        
        tmpList = [1,1]
        for i in range(0,n-1):
            x = tmpList[-1] + tmpList[-2]
            tmpList.append(x)
        # print tmpList
        return tmpList[-1]
           

拓展：

如果你可以一次性跳1~n階，那麼跳完n階台階有多少種跳法？

設f(n)為n階台階的情況下，所有不同的跳法方法的總和!
1.如果在n-1階跳一階，那麼就有 f(n-1) 種跳法；
2.如果在n-2階跳二階，那麼就有 f(n-2) 種跳法；
3.如果在n-3階跳一階，那麼就有 f(n-3) 種跳法；
...
n.如果在n-n階跳一階，那麼就有 f(n-n) 種跳法；

假定f(0) = 1，已知一階台階時，跳法隻有一種，是以f(1) = 1，是以f(2) = 1+1 = 2
得：　　f(n) = f(n-1)+f(n-2)+f(n-3)...+...+f(n-(n-1))+f(n-n)
       f(n) = f(n-1)+f(n-2)+f(n-3)+...+f(0)

又：　　f(n-1) = f(n-2)+f(n-3)...+...+f(0)
　　　　f(n-2) = f(n-3)+f(n-4)...+...+f(0)

則：　　f(n) = 2 * f(n-1)
　　　　　　 = 2^2 * f(n-2)
　　　　　　 = 2^(n-2) * f(2) 

最終結果f(n) = 2**(n-1)