Leetcode # 808. Soup Servings

https://leetcode.com/problems/soup-servings

Solution: DP, Bottom-Up

湯_a 數量為 n_a ，湯_b 數量為 n_b
m_a := ceil(n_a / 25)
m_b := ceil(n_b / 25)
dp[m_a][m_b] 則為回傳的答案

1. dp[0][0] = 0.5
2. m_a == 0, m_b > 0 ⇒ dp = 1
3. m_a > 0, m_b == 0 ⇒ dp = 0 

\begin{align}
dp[m_a][m_b] = \frac{1}{4}( & dp[\mathop{max}(0, m_a – 4)][m_b] \\
+ & dp[\mathop{max}(0, m_a – 3)][\mathop{max}(0, m_b – 1)] \\
+ & dp[\mathop{max}(0, m_a – 2)][\mathop{max}(0, m_b – 2)] \\
+ & dp[\mathop{max}(0, m_a – 1)][\mathop{max}(0, m_b – 3)] )
\end{align}

又，1 >= dp[m_a][m_b] >= 0
⇒ dp[m + 1][m + 1] >= dp[m][m]

加上本題許可的誤差 10^-5 
當 dp[m][m] > 0.99999 == 1 – 0.00001
dp[m + k][m + k], k = 1, 2, 3, … 便可直接回傳為 1

Time Complexity: O(len(n) ** 2)O(1)
Space Complexity: O(len(n) ** 2)O(1)
(The input and output generally do not count towards the space complexity.)

令 ε = 10^-5 為誤差容忍 (error tolerance)
當 m₀ 滿足 dp[m₀][m₀] > 1 − ε便進入了誤差容忍的範圍
這使得我們有個常數上限，所以 time/space complexity 皆為 O(1)

class Solution:
  def soupServings(self, n: int) -> float:
    m = ceil(n / 25)
    dp = [[0.5]]
    serving = [
      [4, 0], [3, 1], [2, 2], [0, 0]
    ]
    def calculate_dp(ma, mb):
      return (dp[max(0, ma - 4)][mb] \
            + dp[max(0, ma - 3)][max(0, mb - 1)]\
            + dp[max(0, ma - 2)][max(0, mb - 2)]\
            + dp[max(0, ma - 1)][max(0, mb - 3)]) / 4

    for ma in range(1, m + 1):
      dp.append([0])
      dp[0].append(1) # 借用給 dp[0][mb]
      for mb in range(1, ma + 1):
        dp[ma].append(calculate_dp(ma, mb))
        if ma != mb:
          dp[mb].append(calculate_dp(mb, ma))
      if dp[ma][ma] > 1 - 1e-5: return 1

    return dp[m][m]

dp 的生成順序

• 建構於 dp = [[0.5]]
• 建構於 dp.append([0])
• 建構於 dp[0].append(1)
• 建構於 dp[ma].append(calculate_dp(ma, mb))
• 建構於 dp[mb].append(calculate_dp(mb, ma))

Solution: DP, Top-Down

如果真的使用 Top-Down 則無法受惠於 error tolerance 因而節省 complexity
有偽裝為 Top-Down 看似使用 recursive function 解答
但實際上在呼叫 recursive function 前已建立好 DP-table

Last Updated on 2023/08/16 by A1go