問題描述
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Subscribe to see which companies asked this question
補(bǔ)充說明：
模擬上臺階，每次能上1級或者2級臺階指黎，給定你一個(gè)臺階個(gè)數(shù)娇斩，問有多少種上臺階的方式誉结。
方案分析
- 這個(gè)問題一眼就讓筆者回憶到上學(xué)和剛畢業(yè)找工作的那段日子了析恢。這個(gè)問題像不像斐波那契數(shù)列漆撞？
- 唯一與斐波那契數(shù)列不同的是n=1和n=2的時(shí)候祟剔。
- 啥也不說了限次，上代碼芒涡，不要用遞歸。
python實(shí)現(xiàn)
class Solution(object):
def climbStairs(self, n):
"""
:type n: int
:rtype: int
"""
if n==1:
return 1
if n==2:
return 2
prev = 2
p_prev = 1
result = 0
for i in range(n-2):
result = prev + p_prev
p_prev = prev
prev = result
return result
