刷題日記(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