刷題日記(4)Climbing Stairs

Rachel Yeh
Dec 23, 2020

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當做例子

Sign up to discover human stories that deepen your understanding of the world.

Free

Distraction-free reading. No ads.

Organize your knowledge with lists and highlights.

Tell your story. Find your audience.

Membership

Read member-only stories

Support writers you read most

Earn money for your writing

Listen to audio narrations

Read offline with the Medium app

Rachel Yeh
Rachel Yeh

Written by Rachel Yeh

Taiwan /Software Engineer / Cryptoer

No responses yet

Write a response