题目要求
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。
示例 1:
输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
示例 2:
输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
思路一
递归的解法,设有n阶楼梯(n>0),那么当爬到第n阶楼梯时,有2种方式,要么是爬1阶到n阶,要么爬2阶到n阶,若求阶公式为f(n),则f(n) = f(n-1) + f(n-2),终止条件是n==1 return 1, n==2 return 2
→_→ talk is cheap, show me the code
# 直接使用递归会AC超时,这里使用一个dict保存中间结果复用,勉强通过
d = dict()
class Solution:
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
if not n:
return 0
if n == 1 or n == 2:
return n
if d.get(n):
return d.get(n)
res = self.climbStairs(n-1) + self.climbStairs(n-2)
d[n] = res
return res
思路二
递归的思想是从后往前,递过去归回来;我们找到了递归公式,也就能写出非递归的实现方式,当n=1时,有1中走法,当n=2时,有2种走法;有了这两个基础,就可以求出n=3时,有f(n-1) + f(n-2) =3种走法;(也就是斐波那契数列)
→_→ talk is cheap, show me the code
class Solution:
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
if not n:
return 0
if n == 1 or n == 2:
return n
pre = 2
prepre = 1
ret = 0
for i in range(3, n+1):
ret = pre + prepre
prepre = pre
pre = ret
return ret
网友评论