從LeetCode學演算法 - 9 Dynamic Programming (2)

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:

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

Example 2:

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: