Python程式：查詢爬樓梯的方法數

假設我們有一個n階樓梯，我們每次可以向上爬1階或2階。我們需要定義一個函式，返回爬上樓梯的唯一方法數。

步驟的順序不能改變，因此每種不同的步驟順序都算作一種方法。如果答案非常大，則將結果模 10^9 + 7

因此，如果輸入為 n = 5，則輸出將為 8，因為有 8 種唯一的方法：

  • 1, 1, 1, 1, 1
  • 2, 1, 1, 1
  • 1, 2, 1, 1
  • 1, 1, 2, 1
  • 1, 1, 1, 2
  • 1, 2, 2
  • 2, 1, 2
  • 2, 2, 1

為了解決這個問題，我們將遵循以下步驟：

  • dp：一個大小為 n+1 的陣列，並用 0 填充
  • dp[1] := 1
  • 對於 i 從 2 到 n+1，執行以下操作：
    • dp[i] := dp[i-1] + dp[i-2]
  • 返回 dp 的最後一個元素模 m

讓我們看看下面的實現，以便更好地理解：

示例

 即時演示

m =(10**9)+7
class Solution:
   def solve(self, n):
      dp=[0 for _ in range(n+2)]
      dp[1]=1
      for i in range(2,n+2):
         dp[i]=dp[i-1]+dp[i-2]
      return dp[-1] % m
ob = Solution()
print(ob.solve(5))

輸入

5

輸出

8

更新於： 2020年10月5日

290 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告