Dynamic Programming21 sections · 916 units
Open in Course

LeetCode 808 Soup Servings - Problem Statement

LeetCode 808

You have two soups, A and B, each with nn ml. Each turn, you pick one of four operations with equal probability: serve (100,0), (75,25), (50,50), or (25,75) ml from (A, B).

The process stops when either soup is empty (or both). Return the probability that A empties first, plus half the probability that both empty at the same time. This looks complex. What should dp track? What's tricky about large nn?