0070. Climbing Stairs (Easy)

Question

You are climbing a staircase. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1

1
2
3
4
5

Input: 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2

1
2
3
4
5
6

Input: 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

分析/解題

題目描述有一個要爬n階才能到頂端的階梯，每次只能爬1階或2階，
試求有多少種不同的方法可以走到頂端。
如果以窮舉的話我們可能需要列很久，
所以這時候又回到了看看是否能找出相互關係的時候了。

我們考慮要爬n階的話，首先要先爬到n-1 階或n-2 階，因為只有一次走1階或一次走2階的選擇。也就是說，走到n階的方法，就相當於走到n-1階的方法和走到n-2階的方法和 。因為最後的步伐已經固定了，我們同時還可以保證這兩個方法的組合之間不會互相重複 (一個最後走1步，一個最後走2步)。

同樣的，走到n-1階的方法=走到(n-2)階的方法+走到(n-3)階的方法，
以此類推拆解，最終我們來到走到第1階的方法跟走到第2階的方法，
分別是1跟2。

我們可以選擇開一個res的陣列，初始化前2階以後，
一路加上去最終得到到第n階的方法數，下面Java的版本因為陣列由0開始，
有刻意將數字不先行化簡，讀者應該可以很簡單地對照。

Java

Python的部分，則採用兩個數s1, s2來輪替使用，可以節省記憶體。
每次應該要做的，是將s1+s2的值擺到s2，而將s2的值擺到s1的位置。
(等於把兩個數代表的位置遞移了一層)
(Java也可以用類似的作法，但需要多宣告一個暫存值進行儲存)

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
（O(N), 依方法而定，
上面Java的寫法需要O(N)，Python的寫法則只需O(1)）

「哪個寫法比較好？」
(以空間節省的角度來說是Python版本的寫法較佳，
但如果我們不止需要算一次的話，執行一次n階，
其實可以將n階以下的走法數量全部記起來，
這樣被讀取的時候可以先查是否可以直接拿結果回傳，
所以反覆執行的效率會變比較好，不過這個就需要再修改一下程式就是了)

從LeetCode學演算法，我們下次見囉，掰~