808. Soup Servings

Link

Solution

Ticks, but not important

When N is greater than 4800, the possibility will be 1.0, since A is decreasing in any operations, so A must reach the end first.

    Map<Integer, Map<Integer, Double>> map = new HashMap<>();
    public double soupServings(int N) {
        return N > 4800 ? 1.0 : helper(N, N);
    }
    
    
    public double helper(int a, int b){
        if(a <= 0 && b <= 0) return 0.5;
        if(a <= 0) return 1;
        if(b <= 0) return 0;
        if(map.containsKey(a) && map.get(a).containsKey(b)){
            return map.get(a).get(b);
        }
        else{
            
            double ret = 0.25*(helper(a-100, b) + 
                              helper(a-75, b-25) +
                              helper(a-50, b-50) + 
                              helper(a-25, b-75));
            
            if(map.containsKey(a)){
                map.get(a).put(b, ret);
            }
            else{
                Map<Integer, Double> v = new HashMap<>();
                v.put(b, ret);
                map.put(a, v);
            }
            return ret;
        }
    }