70. Climbing Stairs

你正在爬樓梯，每步可選擇一階或兩階，如果樓梯有 n 階，你有幾種上樓的方法。

https://leetcode.com/problems/climbing-stairs/

範例
Input: n = 3
Output: 3
Explanation: 有三種方法能上樓
1. 1步 + 1步 + 1步
2. 1步 + 2步
3. 2步 + 1步

可以反向來思考，假入我們有 5 階的樓梯，當階梯走完的前一步，我們應該是站在第 4 階或第 3 階，所以第 5 階的上樓方法，其實就是第 4 階和第 3 階上樓方法的總和。

寫成算式即為F(5) = F(4) + F(3)，用代數替換F(n) = F(n-1) + F(n-2)就是公式解了。

但如果直接使用climbStairs(n) = climbStairs(n-1) + climbStairs(n-2)的遞迴來處理，時間複雜度會太高。觀察公式能發現每一個值都是前兩次的總和，那只需要每次計算完都將結果記錄下來，等下一階時直接取出前面的紀錄相加即可。這種重複出現的子問題，我們可使用記憶體來降低時間複雜度的做法就是DP(Dynamic Programming)。

	public int climbStairs(int n) {

		// 若一階或兩階不用計算，直接回傳結果
		if (n == 1)
			return 1;
		if (n == 2)
			return 2;

		int[] tmp = new int[n];

		tmp[0] = 1;
		tmp[1] = 2;

		for (int i = 2; i < n; i++) {
			// 將計算結果記錄下來，並從中取用
			tmp[i] = tmp[i - 1] + tmp[i - 2];
		}

		return tmp[n - 1];
	}