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 int getPossibleWays(final int n) {
int[] memo = new int[n + 1];
return helper(n, memo);
}
private static int helper(int i, int[] memo) {
if(i == 0 || i == 1) return 1;
if(i ==2) return 2;
if(i >=3 && memo[i] == 0) {
memo[i] = helper(i -1, memo) + helper(i -2, memo) + helper(i -3, memo);
}
return memo[i];
}