.jpeg)
You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Example 1:
1
2
3
4
5
| Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps
|
Example 2:
1
2
3
4
5
6
| Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step
|
1
2
3
4
5
6
| f(1)=1 1
f(2)=2 11 2
f(3)=3 //f(1)+f(2) 111 12 21
f(4)=5 //f(2)+f(3) 1111 112 211 121 22
f(5)=8 //f(3)+f(4) 11111 2111 1211 1121 1112 221 122 212
f(n)=f(n-2)+f(n-1) Fibonacci
|
每次爬1或2格，有幾種方法可以到終點，一開始不知道就先把例子都列出來找規律，最後知道 f(n)=f(n-2)+f(n-1)，這不是fiboncci嗎！知道規律就好辦了。
1
2
3
4
5
6
7
| T: O(n), S: O(1)
class Solution:
def climbStairs(self, n):
a,b = 1,0
for _ in range(n):
a,b = a+b,a
return a
|