070.Climbing Stairs

Posted on | In

Solution 1: time limit exceeded

Time: O(2^n)
I forget to remove “static” on ways and it accumulates the results of all test cases. 

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    int ways = 0;
    public synchronized int climbStairs(int n) {
        if (n > 1) 
          climbStairs(n - 2);
        if (n > 0) 
          climbStairs(n - 1);
        if (n == 0)
          ways++;
        return ways;
    }
}

A better alternative

1
2
3
4
5
public int climbStairs(int n) {
    if(n == 0 || n == 1) 
        return 1;
    return climbStairs(n-1) + climbStairs(n-2);
}

Solution 2: accepted 0ms

Time: O(n)
Straight fibonacci: f(n) = f(n-1) + f(n-2) 

1
2
3
4
5
6
7
8
9
10
11
12
public int climbStairs(int n) {
    if(n < 3) return n;
    int f1 = 1;
    int f2 = 2;
    for(int i = 3; i <= n; i++) {
        int temp = f2;
        f2 += f1;
        f1 = temp;
    }
    return f2;
}