808.分汤

链接：808.分汤
难度：Medium
标签：数学、动态规划、概率与统计
简介：有 A 和 B 两种类型 的汤。当两种类型的汤都分配完时，停止操作。

题解 1 - cpp

• 编辑时间：2022-11-21
• 执行用时：4ms
• 内存消耗：6.2MB
• 编程语言：cpp
• 解法介绍：当 i=0,j=0 时完成同时分配的概率/2=0.5，当 i>0,j=0 时概率 0，当 i=0,j>0 是完成 A 分配概率 1。

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

题解 2 - cpp

• 编辑时间：2022-11-21
• 执行用时：4ms
• 内存消耗：9.3MB
• 编程语言：cpp
• 解法介绍：同上，dfs 记忆化。

class Solution {
public:
    double soupServings(int n) {
        n = ceil(1.0 * n / 25);
        if (n > 179) return 1.0;
        unordered_map<int, unordered_map<int, double>> m;
        function<double(int, int)> dfs= [&m, &dfs](int a, int b) {
            if (m.count(a) && m[a].count(b)) return m[a][b];
            if (a <= 0 && b > 0) return m[a][b] = 1.0;
            if (a <= 0 && b <= 0) return m[a][b] = 0.5;
            if (a > 0 && b <= 0) return m[a][b] = 0.0;
            return m[a][b] = (
                dfs(a - 4, b) +
                dfs(a - 3, b - 1) +
                dfs(a - 2, b - 2) +
                dfs(a - 1, b - 3)
            ) / 4;
        };
        return dfs(n, n);
    }
};