Dynamic Programming21 sections · 916 units
Open in Course

LeetCode 808 Soup Servings - Transition

Four operations

Four operations with equal probability 0.250.25:

1.1. Serve (4,0)(4, 0): go to state (a−4,b)(a-4, b)

2.2. Serve (3,1)(3, 1): go to state (a−3,b−1)(a-3, b-1)

3.3. Serve (2,2)(2, 2): go to state (a−2,b−2)(a-2, b-2)

4.4. Serve (1,3)(1, 3): go to state (a−1,b−3)(a-1, b-3) Transition: dp[a][b]=0.25⋅(dp[a−4][b]+dp[a−3][b−1]+dp[a−2][b−2]+dp[a−1][b−3])dp[a][b] = 0.25 \cdot (dp[a-4][b] + dp[a-3][b-1] + dp[a-2][b-2] + dp[a-1][b-3])

This formula tells you how to compute dp[a][b] from dp values at smaller amounts. Getting this right is the core of DP.