70. Climbing Stairs

[fockspaces]

Example 1:

Input: n = 2 Output: 2 Explanation: There are two ways to climb to the top.

1. 1 step + 1 step
2. 2 steps Example 2:

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

Constraints:

1 <= n <= 45

[fockspaces]

先用 1D array模擬爬梯子遞移關係，之後簡化成O(1)

class Solution {
public:
    int climbStairs(int n) {
        int prev = 1, cur = 1;
        for(int i = 2; i <= n; i++) {
            int temp = cur;
            cur = cur + prev;
            prev = temp;
        }
        return cur;
    }
};