Skip to content

808. Soup Servings 👎

  • Time: $O(1)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  double soupServings(int n) {
    return n >= 4800 ? 1.0 : dfs((n + 24) / 25, (n + 24) / 25);
  }

 private:
  vector<vector<double>> mem =
      vector<vector<double>>(4800 / 25, vector<double>(4800 / 25));

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
  public double soupServings(int n) {
    return n >= 4800 ? 1.0 : dfs((n + 24) / 25, (n + 24) / 25);
  }

  private double[][] mem = new double[4800 / 25][4800 / 25];

  private double dfs(int a, int b) {
    if (a <= 0 && b <= 0)
      return 0.5;
    if (a <= 0)
      return 1.0;
    if (b <= 0)
      return 0.0;
    if (mem[a][b] > 0)
      return mem[a][b];
    return mem[a][b] =
               0.25 * (dfs(a - 4, b) + dfs(a - 3, b - 1) + dfs(a - 2, b - 2) + dfs(a - 1, b - 3));
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def soupServings(self, n: int) -> float:
    @functools.lru_cache(None)
    def dfs(a: int, b: int) -> float:
      if a <= 0 and b <= 0:
        return 0.5
      if a <= 0:
        return 1.0
      if b <= 0:
        return 0.0
      return 0.25 * (dfs(a - 4, b) +
                     dfs(a - 3, b - 1) +
                     dfs(a - 2, b - 2) +
                     dfs(a - 1, b - 3))

    return 1 if n >= 4800 else dfs((n + 24) // 25, (n + 24) // 25)