808. Soup Servings

Description

Solution

In this problem, because all soup are decresed in multiple 25, so we could divid N by 25 then do dp on each one step.

dp[i] [j] -> the desired value with i ml and j ml soup.

dp[i][j] = 0.25 * (dp[i-4][j] + dp[i-3][j-1] + dp[i-2][j-2] + dp[i-1][j-3])

And we note the corner case are:

dp[i][j] = 0.5 (for i <= 0 and j <= 0)
dp[i][j] = 1 (for i = 0, j >= 1)
dp[i][j] = 0 (for i >= 1, j = 0)

Code

class Solution {
public:
    double soupServings(int n) {
        n = ceil(1.0 * n / 25);
        if(n >= 500) return 1;
        vector<vector<float>> dp(n+1, vector<float>(n+1));
        //dp[i][j] = 0.25 * (dp[i-4][j] + dp[i-3][j-1] + dp[i-2][j-2] + dp[i-1][j-3])
        dp[0][0] = 0.5;
        for(int i = 1; i <= n; i++){
            dp[0][i] = 1;
            dp[i][0] = 0;
        }
        for(int i = 1; i <=n ;i++){
            for(int j = 1; j <= i; j++){
                dp[i][j] = 0.25 * (dp[max(0, i - 4)][j] + dp[max(0, i - 3)][j-1] + dp[max(0, i - 2)][max(0, j-2)] + dp[i-1][max(0, j-3)]);
                dp[j][i] = 0.25 * (dp[max(0, j - 4)][i] + dp[max(0, j - 3)][i-1] + dp[max(0, j - 2)][max(0, i-2)] + dp[j-1][max(0, i-3)]);
            }
        }
        return dp[n][n];
    }
};