python——Leetcode 70. 爬樓梯

NO IMAGE
1 Star2 Stars3 Stars4 Stars5 Stars 給文章打分!
Loading...

題目

假設你正在爬樓梯。需要 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 步

解決問題思路

反著考慮,有幾種方案到第i階樓梯,答案是2種:

  1. 第i-1階樓梯經過一步
  2. 第i-2階樓梯經過兩步

假設count(i)表示到第i階樓梯方案的個數,則count(i) = count(i-1) count(i-2)
第一階是1種,第二階是2種。程式碼如下:

class Solution:
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
count = [1,2]
for i in range(2,n):
count.append(count[i-1] count[i-2])
return count[n-1]

相關文章

程式語言 最新文章