Leetcode 70.爬樓梯（Climbing Stairs）

Leetcode 70.爬樓梯

1 題目描述（Leetcode題目連結）

  假設你正在爬樓梯。需要 n 階你才能到達樓頂。每次你可以爬 1 或 2 個台階。你有多少種不同的方法可以爬到樓頂呢？（注意：給定 n 是一個正整數）

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

2 題解

  可以一次走一步或一次走兩步，可以使用動态規劃來解決問題可以定義 D P [ i ] DP[i] DP[i]為有 i i i層樓梯的時候的最多走法，是以走法可以根據第 i − 1 i-1 i−1和 i − 2 i-2 i−2層樓梯得到，狀态轉移方程為：

D P [ i ] = D P [ i − 1 ] + D P [ i − 2 ] DP[i] = DP[i-1]+DP[i-2] DP[i]=DP[i−1]+DP[i−2]

觀察方程可以發現其實就是斐波那契數列。

class Solution:
    def climbStairs(self, n: int) -> int:
        Dif_ways = [0,1,2]
        for i in range(3,n+1):
            Dif_ways.append(Dif_ways[-1] + Dif_ways[-2])
        return Dif_ways[n]