【每日一题Day34】LC808分汤 | 动态规划 记忆化搜索

分汤【LC808】

有 A 和 B 两种类型 的汤。一开始每种类型的汤有 n 毫升。有四种分配操作：

1. 提供 100ml 的 汤A 和 0ml 的 汤B 。
2. 提供 75ml 的 汤A 和 25ml 的 汤B 。
3. 提供 50ml 的 汤A 和 50ml 的 汤B 。
4. 提供 25ml 的 汤A 和 75ml 的 汤B 。

当我们把汤分配给某人之后，汤就没有了。每个回合，我们将从四种概率同为 0.25 的操作中进行分配选择。如果汤的剩余量不足以完成某次操作，我们将尽可能分配。当两种类型的汤都分配完时，停止操作。

注意 不存在先分配 100 ml 汤B 的操作。

需要返回的值： 汤A 先分配完的概率 + 汤A和汤B 同时分配完的概率 / 2。返回值在正确答案 10-5 的范围内将被认为是正确的。

好难…是我做不出来的题 至少也努力看题解并总结了

• 思路：

  • 由于四种分配方式都是25的倍数，因此可以将n除以25，并向上取整。那么四类操作可以等价为

    1. 提供 4ml 的 汤A 和 0ml 的 汤B
    2. 提供 3ml 的 汤A 和 1ml 的 汤B
    3. 提供 2ml 的 汤A 和 2ml 的 汤B
    4. 提供 1ml 的 汤A 和 3ml 的 汤B

  • 当n较小时使用动态规划，求出最终概率，定义dp[i][j]为初始状态当汤A有i毫升，汤B有j毫升时，概率p为dp[i][j]。

  • 比如，当n=4时，我们所需要返回的结果即为dp[4][4]，其概率取决于dp[0][4]、dp[1][3]、dp[2][2]、dp[3][1]
    $$dp[4][4]=(dp[0][4]+dp[1][3]+dp[2][2]+dp[3][1])/4$$
    因此，从dp[0][0]到dp[n][n]的过程，可以想象成一个乘汤的过程

    • 注意：根据题意定义dp初始状态

  • 当n足够大的时候，根据汤 A平均会被分配的份数期望为 $E(A)=(4+3+2+1)\times 0.25=2.5$ ，汤 B 平均会被分配的份数期望为$E(B)=(0+1+2+3)\times 0.25=1.5$。因此在 n 非常大的时候，汤 A会有很大的概率比 B先分配完，汤 A被先取完的概率应该非常接近 1。由于返回值在正确答案 10⁻⁵的范围内将被认为是正确的，通过实际计算可以确定当$n\ge 179\ast 25$时，只需输出1作为答案即可

动态规划实现

记概率$p$= 汤A 先分配完的概率 + 汤A和汤B** 同时分配完的概率 / 2

1. 确定dp数组（dp table）以及下标的含义

   dp[i][j]:汤A剩余i毫升，汤B剩余j毫升时所需要的概率大小， 即汤A 先分配完的概率 + 汤A和汤B 同时分配完的概率 / 2

   或者说初始状态当汤A有i毫升，汤B有j毫升时，概率p为dp[i][j]

2. 确定递推公式

   当数组下标越界时，将下标视为0
   $$dp[i][j]=(dp[i-4][j]+dp[i-3][j-1]+dp[i-2][j-2]+dp[i-1][j-3])/4$$

3. 如何初始化

   • 当$i>0,j=0$，此时汤A还未分配完，因此根据$p$的定义，$dp[i][0]=0$;
   • 当$i=0,j=0$，此时汤A和汤B均分配，因此根据$p$的定义，$dp[0][0]=0.5$;
   • 当$i=0,j>0$，此时汤A分配完，汤B未分配完，因此根据$p$的定义，$dp[0][j]=1.0$;

4. 确定遍历顺序

   由dp公式可知，外层正序遍历i，内层正序遍历j

5. 举例推导dp数组

• 代码 ：DP 自下而上 计算了许多不需要的结果

  class Solution {
      public double soupServings(int n) {
          n = (int) Math.ceil((double) n / 25);
          if (n >= 179) {
              return 1.0;
          }
          double[][] dp = new double[n + 1][n + 1];
          dp[0][0] = 0.5;
          for (int j = 1; j <= n; j++) {
              dp[0][j] = 1.0;
          }
          for (int i = 1; i <= n; i++) {
              for (int j = 1; j <= n; j++) {
                  dp[i][j] = (dp[Math.max(0, i - 4)][j] + dp[Math.max(0, i - 3)][Math.max(0, j - 1)] + dp[Math.max(0, i - 2)][Math.max(0, j - 2)] + dp[Math.max(0, i - 1)][Math.max(0, j - 3)]) / 4.0;
              }
          }
          return dp[n][n];
      }
  }
  
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20

  • 复杂度

    • 时间复杂度：$O(C^2)$，因为存在常数 C，在这里我们可以取 C=179，使得当 n>C 时，所求的概率和 1的误差在 10⁻⁵
      以内，我们可以直接返回，需要的时间为 O(1)；当 n≤C 时，我们需要的时间复杂度为 O(n²)，因此总的时间复杂度为O(C²)
    • 空间复杂度：$O(C^2)$

记忆化搜索 自上而下

减少许多无效状态的计算

class Solution {
    private double[][] memo;

    public double soupServings(int n) {
        n = (int) Math.ceil((double) n / 25);
        if (n >= 179) {
            return 1.0;
        }
        memo = new double[n + 1][n + 1];
        return dfs(n, n);
    }

    public double dfs(int a, int b) {
        if (a <= 0 && b <= 0) {
            return 0.5;
        } else if (a <= 0) {
            return 1;
        } else if (b <= 0) {
            return 0;
        }
        if (memo[a][b] == 0) {
            memo[a][b] = 0.25 * (dfs(a - 4, b) + dfs(a - 3, b - 1) + dfs(a - 2, b - 2) + dfs(a - 1, b - 3));
        }
        return memo[a][b];
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/soup-servings/solutions/1981704/fen-tang-by-leetcode-solution-0yxs/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

• 复杂度
  • 时间复杂度：$O(C^2)$，因为存在常数 C，在这里我们可以取 C=179，使得当 n>C 时，所求的概率和 1的误差在 10⁻⁵ 以内，我们可以直接返回，需要的时间为 O(1)；当 n≤C 时，我们需要的时间复杂度为 O(n²)，因此总的时间复杂度为O(C²)
  • 空间复杂度：$O(C^2)$