Stairs

You are climbing a stair case and it takes A 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?

The first and the only argument contains an integer A, the number of steps.

Return an integer, representing the number of ways to reach the top.

1 <= A <= 36

Input 1:

A = 2 Output 1:

2 Explanation 1:

[1, 1], [2] Input 2:

A = 3 Output 2:

3 Explanation 2: 

[1 1 1], [1 2], [2 1]

Solution 1:

Time: O(n)
Space: O(n)

public class Solution {
    public int climbStairs(int A) {
        int[] dp = new int[A + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= A; i ++) {
            dp[i] = dp[i - 2] + dp[i - 1];
        }
        return dp[A];
    }
}

Solution 2:

Time: O(n)
Space: O(1)

public class Solution {
    public int climbStairs(int A) {
        int prevPrev = 1;
        int prev = 1;
        for (int i = 2; i <= A; i ++) {
            int oldPrev = prev;
            prev = prev + prevPrev;
            prevPrev = oldPrev;
        }
        return prev;
    }
}