Friday, November 7, 2014

Facebook: Climb a flight

Write a function to compute the number of ways to climb a flight of n steps. Taking 1, 2, or 3 steps at a time. Do it in linear time and constant spaces. 

For example, n = 3.
1   1   1
1   2
2   1
3

Understand the problem:
The problem is similar to climb stairs in Leetcode. The mainly difference is we could take 1, 2, 3 steps at a time. So we could have recursive and DP solutions.

Recursive Solution:
public class Solution {
    public int climbStairs(int n) {
        if (n <= 0) {
            return 0;
        }
        
        return climbStairsHelper(n);
    }
    
    private int climbStairsHelper(int n) {
        if (n < 0) {
            return 0;
        }
        
        if (n == 0) {
            return 1;
        }
        
        return climbStairsHelper(n - 1) + climbStairsHelper(n - 2) + climbStairsHelper(n - 3);
    }

    public static void main(String[] args) {
      Solution sol = new Solution();

      int result = sol.climbStairs(4);

      System.out.println(result);
    }
}


DP Solution:

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

A const-space Solution:
Since this problem requires for a constant space solution, we may think of how to avoid the use of the DP array. If you notice about the dp transit function, you may find out that actually dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]. So we may not need to use an array to store the num of steps, just several variables are enough. The solution is simply based on the observation that for dp problem, the state i may only rely on previous states, e.g. i -1, i - 2, etc. 

Code (Java):
public class Solution {
    public int climbStairs(int n) {
        if (n <= 0) {
            return 1;
        }
        
        if (n == 1) {
            return 1;
        }
        
        if (n == 2) {
            return 2;
        }
        
        int dp_i = 0;
        int dp_i_1 = 2;
        int dp_i_2 = 1;
        int dp_i_3 = 1;

        
        for (int i = 3; i <= n; i++) {
            dp_i = dp_i_1 + dp_i_2 + dp_i_3;
            dp_i_3 = dp_i_2;
            dp_i_2 = dp_i_1;
            dp_i_1 = dp_i;
        }
        
        return dp_i;
    }
}

Summary:
This is a really interesting problem. The take-away message is for many DP questions, if the current state only replies on a fixed set of previous states, we may not need to create a DP array, just use several variables to save the states is fine. 

No comments:

Post a Comment