假设你正在爬楼梯。需要 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):
"""
:type n: int
:rtype: int
"""
steps = [1, 2]
if n == 1 or n == 2:
return n
for i in xrange(2, n):
sn = steps[i-1] + steps[i-2]
steps.append(sn)
return steps[-1]
思路:仔细分析就可以得出当前的台阶数是上一阶台阶数和上上阶台阶数之和,因为当前台阶只有可能从上一层或者上上层到达,所以求出上一层或者上上层的台阶数就可以了,依此类推,就是一个叠加的过程。