Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Soup Servings
Bookmark
Memoization
Bottom-Up DP
Input
n = 50
n = 100
n = 25
n = 75
n = 150 (cache hits)
Custom
n
=
50
n =
50
ml
m =
2
B units left →
A units left →
0
0
1
1
2
2
four pours, each ¼ chance: (100,0) (75,25) (50,50) (25,75) ml of (A,B)
n =
50
ml
m =
2
B units left →
A units left →
0
0
1
1
2
2
four pours, each ¼ chance: (100,0) (75,25) (50,50) (25,75) ml of (A,B)
n =
50
ml
m =
2
B units left →
A units left →
0
0
1
1
2
2
n =
50
ml
m =
2
B units left →
A units left →
0
0
1
1
2
2
call stack
dp(2,2)
1 call
n =
50
ml
m =
2
B units left →
A units left →
0
0
1
1
2
2
call stack
dp(2,2)
1 call
n =
50
ml
m =
2
B units left →
A units left →
0
0
1
1
2
2
call stack
dp(-2,2)
dp(2,2)
2 calls
n =
50
ml
m =
2
B units left →
A units left →
0
0
1
1
2
2
call stack
dp(-1,1)
dp(2,2)
3 calls
n =
50
ml
m =
2
B units left →
A units left →
0
0
1
1
2
2
call stack
dp(0,0)
dp(2,2)
4 calls
n =
50
ml
m =
2
B units left →
A units left →
0
0
1
1
2
2
call stack
dp(1,-1)
dp(2,2)
5 calls
n =
50
ml
m =
2
dp[2][2] =
0.625
B units left →
A units left →
0
0
1
1
2
2
.625
1
1
0
call stack
dp(2,2)
5 calls
¼·(
1.000
+
1.000
+
0.500
+
0.000
) =
0.625
n =
50
ml
m =
2
B units left →
A units left →
0
0
1
1
2
2
.625
result = 0.62500
algo
master
.
io
Step:
Soup Servings: both soups start with n = 50 ml. Find P(A empties first) + ½·P(both empty together).
0 / 22
Input
n = 50
n = 100
n = 25
n = 75
n = 150 (cache hits)
Custom
n
=
50
0 / 22
algo
master
.
io
Step:
Soup Servings: both soups start with n = 50 ml. Find P(A empties first) + ½·P(both empty together).
