808. Soup Servings

It is a very very good question

Version #1 Memorized DFS
The key is to properly define the state
The base case if very very tricky

Time O(N^2) Since there are total of N(a) * N(b) states


[2ND TRY]

70.19 %
class Solution {
    public double soupServings(int N) {
if (N > 5000) return 1;
int a = (int) Math.ceil(N / 25.0);
int b = (int) Math.ceil(N / 25.0);
double[][] dp = new double[a + 1][b + 1];
for (int i = 0; i <= a; i++) {
Arrays.fill(dp[a], -1);
}
return dfs(a, b, dp);
}

private double dfs(int a, int b, double[][] dp) {
if (a >= 0 && b >= 0 && dp[a][b] > 0) {
return dp[a][b];
}
if (a <= 0) {
if (b <= 0) { // A,B become empty at the same time
return 0.5;
} else { // A be empty first
return 1;
}
} else if (b <= 0){ // B be empty first
return 0;
}
dp[a][b] = 0.25 * (dfs(a - 4, b, dp) + dfs(a - 3, b - 1, dp) + dfs(a - 2, b - 2, dp) + dfs(a - 1, b - 3, dp));
return dp[a][b];
}
}

[1ST TRY]
65.80 %
class Solution {
    public double soupServings(int N) {
        if (N > 5000) return 1.0;
        // Since the states are discrete,  we should solve it by memorized dfs instead of dp
        // we use 25ml as one serve, if the remaining amount is less than 25, it is also treated as one serve
        int n = N / 25 + (N % 25 == 0 ? 0 : 1);
        // we use the remaining quantity to represent the state
        return dfs(n, n, new HashMap<>());
    }
 
    private double dfs(int a, int b, Map<Integer, Map<Integer, Double>> map) {
        // if we have a remaining and b remaming
        if (a <= 0 && b <= 0) return 0.5;
        if (a <= 0) return 1.0;
        if (b <= 0) return 0.0;
     
        if (map.containsKey(a) && map.get(a).containsKey(b)) {
            return map.get(a).get(b);
        }
        // Serve 100 ml of soup A and 0 ml of soup B   A4 B0
        // Serve 75 ml of soup A and 25 ml of soup B   A3 B1
        // Serve 50 ml of soup A and 50 ml of soup B   A2 B2
        // Serve 25 ml of soup A and 75 ml of soup B   A1 B3
        double prob = 0.25 * (dfs(a - 4, b, map) + dfs(a - 3, b - 1, map) + dfs(a - 2, b - 2, map) + dfs(a - 1, b - 3, map));
        Map<Integer, Double> aMap = map.getOrDefault(a, new HashMap<>());
        aMap.put(b, prob);
        map.put(a, aMap);
        return prob;
    }
}