[LeetCode] Problem 70 - Climbing Stairs

Posted on | In ,

You are climbing a stair case. It takes n 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?

Note

Given n will be a positive integer.

Example

No.1

Input: 2

Output: 2

Explanation: There are two ways to climb to the top.

  1. 1 step + 1 step
  2. 2 steps

No.2

Input: 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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// O(n) runtime, O(1) space – Dynamic programming
public int climbStairs(int n) {
    int[] dp = new int[2];
    dp[0] = 1;
    dp[1] = 1;

    for (int i = 2; i <=n; i++) {
        int current = dp[0] + dp[1];
        dp[0] = dp[1];
        dp[1] = current;
    }

    return dp[1];
}