0808-soup-servings.py

# 808. Soup Servings
# Medium
# https://leetcode.com/problems/soup-servings

importmath;

classSolution:
defsoupServings(self, n: int) ->float:
m=math.ceil(n/25)
dp= {}

defcalculate_dp(i, j):
return (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)]) /4

dp[0] = {0: 0.5}
forkinrange(1, m+1):
dp[0][k] =1
dp[k] = {0: 0}
forjinrange(1, k+1):
dp[j][k] =calculate_dp(j, k)
dp[k][j] =calculate_dp(k, j)
ifdp[k][k] >1-1e-5:
return1
returndp[m][m]

# ********************#
# TEST #
# ********************#

importunittest

classTestStringMethods(unittest.TestCase):
deftest_addBinary(self):
self.assertEqual(Solution.soupServings(self, 50), 0.62500)
self.assertEqual(Solution.soupServings(self, 100), 0.71875)


if__name__=='__main__':
unittest.main()