楼主:
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：