假设你正在爬楼梯。需要 n 步你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
- 1 步 + 1 步
- 2 步
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
- 1 步 + 1 步 + 1 步
- 1 步 + 2 步
- 2 步 + 1 步
实际上是斐波那契数列
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]
下面的方法可以计算出所有的走法，但是超时
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])
