原题链接：Climbing Stairs
本题是斐波那契数列，先上代码：
class Solution:
# @param {integer} n
# @return {integer}
def climbStairs(self, n):
if n == 1:
return 1
if n == 2:
return 2
a, b = 1, 1
while n:
a, b = b, a + b
n -= 1
return a
分析问题：
我先在纸上写下前几步的结果，观察规律。当n=1时，方法数为1；当n=2时，方法数为2；当n=3时，（由于我们只能选择上1层或者2层）我们先选择开始走1层这个方案，剩下两层，那么方法数就是n=2的方法数，然后再选择开始走2层这个方案，剩下一层，那么方法数就是n=1的方法数，因此n=3时的总方法数就是n=1时的方法数加上n=2时的方法数；
n=4时，先走1层的话，剩下3层，方法数为n=3，先走2层的话，剩下2层，方法数为n=2，因此n=4时的总方法数为n=2时的方法数加上n=3时的方法数。
由此，可发现规律，即是斐波那契数列。
网友评论