package hackerrank.ctci;

import java.util.Scanner;

/**
 * https://www.hackerrank.com/challenges/ctci-recursive-staircase
 */
public class DavisStaircase {
    private static int staircase(int n) {
        // TODO:
        return 0;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int s = in.nextInt();
        for (int a0 = 0; a0 < s; a0++) {
            int n = in.nextInt();
            System.out.println(staircase(n));
        }
    }
}

@@ -19,16 +19,64 @@
 .ctci;%0A%0A
+import java.util.HashMap;%0Aimport java.util.Map;%0A
 import j
@@ -93,16 +93,16 @@
 canner;%0A
-
 %0A/**%0A * 
@@ -252,33 +252,472 @@
     
-// TODO:%0A        return 0
+return staircase(n, new HashMap%3C%3E());%0A    %7D%0A%0A    private static int staircase(int n, Map%3CInteger, Integer%3E memo) %7B%0A        if (n %3C 0) %7B%0A            return 0;%0A        %7D%0A        if (n == 0) %7B%0A            return 1;%0A        %7D%0A        if (memo.containsKey(n)) %7B%0A            return memo.get(n);%0A        %7D%0A        int total = 0;%0A        for (int i = 1; i %3C= 3; i++) %7B%0A            total += staircase(n - i, memo);%0A        %7D%0A        memo.put(n, total);%0A        return total
 ;%0A  

Solve Davis' Staircase