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.

CC150-9.1.java

package POJ;

public class Main{
 
	/**
	 * 
	 * 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 possible ways the child can run up the stairs.
	 * 
	 * 
	 */
	public static void main(String[] args) {
		Main so = new Main();
		int stairCount = 3;
		int[] map = new int[stairCount + 1];
		for (int i = 0; i < stairCount + 1; i++) {
			map[i] = -1;
		}
		System.out.println(so.countWaysDP(stairCount, map));
		System.out.println(so.countWaysRecursive(stairCount));
	}

	public int countWaysDP(int n, int[] map) {
		if (n < 0)
			return 0;
		else if (n == 0)
			return 1;
		else if (map[n] > -1)
			return map[n];
		else {
			map[n] = countWaysDP(n - 1, map) + countWaysDP(n - 2, map)
					+ countWaysDP(n - 3, map);
			return map[n];
		}
	}

	public int countWaysRecursive(int n) {
		if (n < 0)
			return 0;
		else if (n == 0)
			return 1;
		else {
			return countWaysRecursive(n - 1) + countWaysRecursive(n - 2)
					+ countWaysRecursive(n - 3);
		}
	}
}