作者:
Rushia (みけねこ的鼻屎)
2022-12-12 09:05:0670. Climbing Stairs
龍大要爬樓梯，他每次可以選擇走一階或走兩階，求出爬到第n階共有幾種走法。
Example :
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
思路：
1.經典的dp題，到第i階的可能走法為從i-1位置走一步加上從i-2位置走兩步，
狀態轉移方程為 dp[i] = dp[i - 1] + dp[i - 2]。
2.因為我們只要知道前兩階共有幾種走法，所以dp只需要維護大小為2的陣列即可，
空間複雜度O(n) ==> O(1)
Java Code：