假設(shè)你正在爬樓梯美侦。需要 n 步你才能到達(dá)樓頂。
每次你可以爬 1 或 2 個(gè)臺(tái)階式撼。你有多少種不同的方法可以爬到樓頂呢踢匣？
注意：給定 n 是一個(gè)正整數(shù)告匠。
示例 1：
輸入： 2
輸出： 2
解釋?zhuān)?有兩種方法可以爬到樓頂。
- 1 步 + 1 步
- 2 步
示例 2：
輸入： 3
輸出： 3
解釋?zhuān)?有三種方法可以爬到樓頂离唬。
- 1 步 + 1 步 + 1 步
- 1 步 + 2 步
- 2 步 + 1 步
實(shí)際上是斐波那契數(shù)列
class Solution(object):
def climbStairs(self, n):
steps = [1, 2]
for i in range(3, n+1):
steps.append(steps[-1] + steps[-2])
return steps[n-1]
下面的方法可以計(jì)算出所有的走法后专，但是超時(shí)
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
steps = [["1"],
["11", "2"]]
if n < 3:
return len(steps[n-1])
for i in range(3, n+1):
last = steps[-1]
temp = []
for s in last:
_left = "1" + s
if _left not in temp:
temp.append(_left)
_right = s + "1"
if _right not in temp:
temp.append(_right)
lastlast = steps[-2]
for s in lastlast:
_left = "2" + s
if _left not in temp:
temp.append(_left)
_right = s + "2"
if _right not in temp:
temp.append(_right)
steps.append(temp)
return len(steps[n-1])
