Question9_1.java

/**
 * 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 possible ways the child can run up the stairs.
 * 
 * Time  Complexity: O(n)
 * Space Complexity: O(n)
 */

public class Question9_1 {
    public int numberOfWays(int totalSteps) {
        if (totalSteps < 0) {
            return 0;
        }
        
        int[] ways = new int[totalSteps + 1];
        ways[0] = 1;
        for (int i = 1; i <= totalSteps; ++i) {
            ways[i] += ways[i -1];
            if (i - 2 >= 0) {
                ways[i] += ways[i - 2];
            }
            if (i -3 >= 0) {
                ways[i] += ways[i - 3];
            }
        }
        
        return ways[totalSteps];
    }
    
    public static void main(String[] args) {
        Question9_1 question9_1 = new Question9_1();
        for (int totalSteps = 0; totalSteps <= 29; ++totalSteps) {
            System.out.println(question9_1.numberOfWays(totalSteps));
        }
    }
}