The Question :Utkarsh being a very talkative child, was scolded by his teacher  multiple times. One day, the teacher became very angry and decided to  give him a very rigorous punishment. He made him stand on the school  field which is X axis.Utkarsh initially stood at X = 0. The teacher asked him to run to X =  N. But, to make the process quick, Utkarsh decided that he will make  jumps of 2 or 3 steps only, i.e., from X = S he can jump to X = S+2 or  X = S+3.Utkarsh decided that he will jump 2 steps with probability P/100 and  jump 3 steps with probability 1-P/100.You need to find the probability that he will reach exactly on X = N.Constraints: 0 < N <= 106  0 <= P <= 100Input Constraints: The first line contains two integer N and P.Output Constraints: Your answer must contain exactly 6 digits after  the decimal point.The SolutionI applied DP using memoization using HashMap ,on large input it gives stackoverflow error at hashmap.containsKey line , please tell why it shows that error and a better way to do memoization here . i have faced this problem many times.import java.util.HashMap;import java.util.Scanner;public class Utkarsh_and_Jumps {    private static double p;    private static HashMap<Integer, Double> dp;    public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        int n = scanner.nextInt();        p = scanner.nextInt();        dp = new HashMap<Integer, Double>();        System.out.println(String.format(%.6g%n, solve(0, n)));    }    private static double solve(int i, int n) {        if (dp.containsKey(i)) {            return dp.get(i);        }        if (i == n) {            return 1;        } else if (i > n) {            return 0;        }        double a = solve(i + 2, n) * (p / 100);        double b = solve(i + 3, n) * (1 - (p / 100));        dp.put(i, a + b);        return a + b;    }}The Input :29194 14The ErrorException in thread main java.lang.StackOverflowError    at java.util.HashMap.hash(HashMap.java:338)    at java.util.HashMap.containsKey(HashMap.java:595)    at Utkarsh_and_Jumps.solve(Utkarsh_and_Jumps.java:24)    at Utkarsh_and_Jumps.solve(Utkarsh_and_Jumps.java:33)
Count number of ways to achieve a sum
java;programming challenge;dynamic programming
You get the StackOverflowError because the solve method is called recursively too many times for large inputs such as 29194.The first time you call solve(0, ...), nothing is already computed, so this will recursively call: * solve(2, ...) and then solve(4, ...), and so on until it reaches 29194 *solve(3, ...)and thensolve(6, ...), and so on until it reaches 29194 However, there's a simple trick to avoid all the recursion: iterate backwards. Call solve(n, ...) (yes, this will call solve(n+2) and solve(n+3), but those will finish fast without recurring). Then, call solve(n-1), then solve(n-2), and so on, until solve(0). Notice how this time all recursive calls will finish in one step, as the values will already be computed and available in dp.So, before your call to solve(0, n), add the following code:for (int i = n; i >= 0; i--) {    solve(i, n);}and you will avoid the StackOverflowError.Here it is in action: http://ideone.com/7Ou8qqNote that this is the smallest change to your code that I could make to get it to run, so it's more like a hack. Optimally, you would change your algorithm to run in reverse order by default.