Leetcode: Climbing Stairs

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?

Understand the problem:
The problem asks for climbing a stair case, which takes n steps to reach the top. Each time you can either climb 1 or 2 steps. How my distinct ways you can climb to the top. 

Note that the problem is very similar to the unique path, where you can either go right or down. So again, we can develop both recursive and DP solutions.

A recursive Solution:

public class Solution {
    public int climbStairs(int n) {
        if (n <= 1) {
            return 1;
        }
        
        return climbStairsHelper(0, n);
    }
    
    private int climbStairsHelper(int cur, int n) {
        if (cur > n) {
            return 0;
        }
        
        if (cur == n) {
            return 1;
        }
        
        return climbStairsHelper(cur + 1, n) + climbStairsHelper(cur + 2, n);
    }
}

Discussion:
Not surprisingly, the solution got the TLE error since the time complexity is in exponential order. So we should naturally think about the DP solution. First think about the recursion-based DP since it requires minimal modifications to the code. 

A recursion-based DP solution:

public class Solution {
    public int climbStairs(int n) {
        if (n <= 1) {
            return 1;
        }
        
        int[] dp = new int[n + 1];
        return climbStairsHelper(0, n, dp);
    }
    
    private int climbStairsHelper(int cur, int n, int[] dp) {
        if (cur > n) {
            return 0;
        }
        
        if (cur == n) {
            return 1;
        }
        
        if (dp[cur] != 0) {
            return dp[cur];
        }
        
        dp[cur] = climbStairsHelper(cur + 1, n, dp) + climbStairsHelper(cur + 2, n, dp);
        
        return dp[cur];
    }
}

Discussion:
Now it passed the OJ test. Now the time complexity becomes O(n) because we only need to calculate the first branch of DFS, which has the depth of n. The rest of them will be repeated value which were cached before. We can still come out an iterative-based DP solution.

Iterative-based DP solution:
Like before, we define a DP array and its transit equation. We define dp[i] as the number of distinct ways from start to start level i. So dp[i] = dp[i - 1] + dp[i - 2]. 

Code (Java) :

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

Summary:This problem is again a classical DP problem. Try to categorize with Unique Path I, II, and minimum path problems together. 

Update on 11/02/14:

A constant-space DP Solution:

public class Solution {
    public int climbStairs(int n) {
        if (n <= 0) {
            return 0;
        }
        
        int dp_i = 1;
        int dp_i_1 = 1;
        int dp_i_2 = 1;
        
        for (int i = 2; i <= n; i++) {
            dp_i = dp_i_1 + dp_i_2;
            dp_i_2 = dp_i_1;
            dp_i_1 = dp_i;
        }
        
        return dp_i;
    }
}