Leetcode Problem 808. Soup Servings

Algorithm

1. Convert the initial ml of soup n to servings m by dividing by 25 and rounding up.
2. Initialize a DP table dp with dimensions (m+1) x (m+1).
3. Set base cases: dp[0][j] = 1 for all j > 0, dp[i][0] = 0 for all i > 0, and dp[0][0] = 0.5.
4. Iterate over the DP table starting from dp[1][1] to dp[m][m].
5. For each cell dp[i][j], calculate its value based on the recurrence relation using the values from the previous operations.
6. If at any point dp[k][k] is greater than 1 - 10^-5, return 1 as the answer.
7. After filling the DP table, return dp[m][m] as the final answer.