Dynamic Programming21 sections · 916 units
Open in Course

LeetCode 808 Soup Servings - State Definition

Remaining amounts

After scaling by 2525, define dp[a][b]dp[a][b] = probability that A empties first (plus half of both empty) given aa units of A and bb units of B remain. Base cases:

1.1. If a0a \leq 0 and b0b \leq 0: both empty simultaneously. Return 0.50.5.

2.2. If a0a \leq 0: A emptied first. Return 11.

3.3. If b0b \leq 0: B emptied first. Return 00. The answer is dp[n/25][n/25]dp[n/25][n/25], rounded up if not divisible. This dp definition has all the information needed to compute the probability from (a, b).