刷題日記（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個台階

以n為6當做例子