countWaysDP

public class countWaysDP {
    public static 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 static int countWaysDP2(int n, int[] map) {
        map[1] = 1; // when n = 1, answer is 1
        map[2] = 2; // when n = 2, answer is 2, (1+1) and (2)
        map[3] = 4; // (1+1+1), (1+2), (2+1), (3)

        for(int i = 4;i <= n; i++)
        {
            map[i] = map[i-1] + map[i-2] + map[i-3];
        }

        return map[n];
    }

    public static 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);
        }
    }

    public static void main(String[] args) {
        for (int i = 0; i < 30; i++) {
            long t1 = System.currentTimeMillis();
            int[] map = new int[30 + 1];
            for (int j = 0; j < map.length; j++) {
                map[j] = -1;
            }
            int c1 = countWaysDP(i, map);
            long t2 = System.currentTimeMillis();
            long d1 = t2 - t1;



            long t3 = System.currentTimeMillis();
            int c2 = countWaysRecursive(i);
            long t4 = System.currentTimeMillis();
            long d2 = t4 - t3;
            System.out.println(i + " " + c1 + " " + c2 + " " + d1 + " " + d2);
        }
    }

}