#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/probability-dp/soup-servings-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/probability-dp/soup-servings-implementation

Repovive

LeetCode 808 Soup Servings - Implementation - Probability DP | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

LeetCode 808 Soup Servings - Implementation

The code

Here's the solution with the large- $n$ improvement:

function soupServings(n)
    if n > 4800 then
        return 1.0
    n := (n + 24) / 25
    size := n + 1
    dp := 2D (two-dimensional) array [size][size], all -1
    return solve(n, n)
function solve(a, b)
    if a ≤ 0 and b ≤ 0 then
        return 0.5
    if a ≤ 0 then
        return 1.0
    if b ≤ 0 then
        return 0.0
    if dp[a][b] ≠ -1 then
        return dp[a][b]
    result := 0.25 × (solve(a-4, b) + solve(a-3, b-1) + solve(a-2, b-2) + solve(a-1, b-3))
    dp[a][b] := result
    return result

Time: $O((n/25)^2)$ for small $n$ . Space: $O((n/25)^2)$ .

Time complexity: $O(N^2)$ .

Space complexity: $O(N^2)$ .