Career cup 9.1

StepCounter.java

package Chapter9;

public class StepCounter {
    public static long countAllWays(int n) {
	long wayCount = 0;
	return step(n, wayCount);
    }

    private static long step(int n, long count) {
	if(n == 0) return count + 1;
	
	if(n > 0)
	    count = step(n-1, count);
	if(n > 1)
	    count = step(n-2, count);
	if(n > 2)
	    count = step(n-3, count);
	
	return count;
    }
    
    private static long countAllWaysMem(int n) {
	long ways[] = new long[n+1];
	ways[0] = 1;
	for(int i = 1; i <= n; i++) {
	    ways[i] = ways[i-1];
	    if(i > 1)
		ways[i] += ways[i-2];
	    if(i > 2)
		ways[i] += ways[i-3];
	}
	
	return ways[n];
    }
    
    public static void main(String[] args) {
	System.out.println(countAllWaysMem(100));
	System.out.println(countAllWays(30));
    }
}