CTCI 9.1

A child is running up a staircase with n steps, and can hop either 1 step, 2 steps, or 3 steps at a time. Implement a method to count how 
many posible ways the child can run up the stairs.

CTCI 9.1-1.java

public static int countWays(int high){
    if(high == 0) return 1;
    else if(high > 0) return (countWays(high - 1) + countWays(high - 2) + countWays(high - 3));
    else return 0;
}

CTCI 9.1-2.java

public static void countWays(int high){
    if(high <= 0) return 0;
    int[] dp = new int[high + 1];
    dp[0] = 1;
    countWays(high, dp);
    return dp[high];
}

public static void countWays(int high, int[] dp){
    if(high < 0) return 0;
    else if(dp[high] > 0) return dp[high];
    else{
        dp[high] = countWays(high - 1, dp) + countWays(high - 2, dp) + countWays(high - 3, dp);
        return dp[high];
    }
}