刷題日記(4)Climbing Stairs
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:
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:
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
Constraints:
1 <= n <= 45
就是個費波那契數列。
此題不是求最優解,是計數問題。
問的是有幾種方式可以達到第n個台階
解題思路
1. 根據題目由於每次只能走1階或2階,所以要到達n階的可能只有n-1和n-2
2. 思考起點:
f(0)=0; 代表第0階走到第0階的方式,原地不動為1
f(1)=1; 代表第0階走到第1階的方式,只有一種方式,跨一步到達第一階
3. F(n)代表了走到第n個台階的總共不同的方式個數,產生了轉移方程式 f(n)=f(n-1)+f(n-2)
(main function)
1. 設定一個list長度為n+1
2. 根據起點設定f[0]=1 以及f[1]=1, 方便後面加下去
3. 開始跑for迴圈,i=2; 因為0 &1 已經有數值了, 當i小於n時, i++; 在迴圈裡f[i]會等於前一格和前前一格的加總
4. 當for迴圈跑完時,list的數值也一路加到n填完了,回傳f[n]就是有幾種方式可以到達第n個台階

