Problem Description

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?

Examples

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:

解析

題目給定一個正整數 n 代表要爬到 第n 階樓梯

假設每次 可以選擇爬 1 階或是 2 階

寫一個演算法算是 爬到第 n 階總共有幾種方式

要看爬到 n 階

可以先思考有幾總可能性

最後一步是走 2 階 也就事前一步事先爬了 n-2 階

最後一步是走 1 階 也就事前一步事先爬了 n-1 階

climb(n) = climb(n-2) + climb(n-1), 對所有 n ≥3