题目:如下图

题目

解题思路:

首先假设:
楼梯数量数列a为:
1、2、3、4、5、6、7…
那么对应的方法数列为b:
1、1、2、3、5、8、13…
假设楼梯数量数列a为等差为1且a[0]=1的等差数列
很明显发现b[0]=1、b[1]=1
那么剩下的b[n]=b[n-1]+b[n-2] , n>2
前两项的和等于第三项

即:
当n=1,n=2 时,方法数为1
当n>2时,方法数为b[n-1]+b[n-2]
(经百度后,其实这种数列为斐波那契数列)

那么思路就很明确了,当楼梯数为1或者2时,方法数为1。
当楼梯数为n(n>3)时,方法数为b[n-1]+b[n-2]。

关于斐波那契数列:链接
下面是python3的详细解题代码:

class Solution:
def climbStairs(self, n: int) -> int:
# b[i] = b[i-1]+b[i-2]
b = []
b.append(1) # 初始状态,只有1阶的时候有一种走法
b.append(2) # 有2阶的时候有两种走法
if n==1:
return 1
if n==2:
return 2
for i in range(2,n):
b.append(b[i-1]+b[i-2])
return b[-1]
分类: 刷题记

发表评论

电子邮件地址不会被公开。 必填项已用*标注