Count number of ways to achieve a sum 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 &lt; N &lt;= 106  0 &lt;= P &lt;= 100
  
  Input Constraints: The first line contains two integer N and P.
  
  Output Constraints: Your answer must contain exactly 6 digits after
  the decimal point.


The Solution

I 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&lt;Integer, Double&gt; dp;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        p = scanner.nextInt();
        dp = new HashMap&lt;Integer, Double&gt;();
        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 &gt; 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 14


The Error

Exception 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)
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 &gt;= 0; i--) {
    solve(i, n);
}


and you will avoid the StackOverflowError.

Here it is in action: http://ideone.com/7Ou8qq

Note 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.