Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Dungeon Game
Bookmark
Brute Force
2D DP
Space Optimized
Input
Example 1
Single Cell
Example 3
2x2 All Negative
2x3 Mixed
Custom
dungeon
=
[-2,-3,3], [-5,-10,1], [10,30,-5]
knight
3x3
knight
princess
-2
-3
+3
-5
-10
+1
+10
+30
-5
calls: 0
smallest starting HP so the knight never drops below 1
knight
3x3
knight
princess
-2
-3
+3
-5
-10
+1
+10
+30
-5
calls: 0
smallest starting HP so the knight never drops below 1
knight
3x3
knight
princess
-2
-3
+3
-5
-10
+1
+10
+30
-5
calls: 2 sum: -7 deepest dip: -7
knight
3x3
knight
princess
-2
-3
+3
-5
-10
+1
+10
+30
-5
calls: 4 sum: 33 deepest dip: -7
knight
3x3
knight
princess
-2
-3
+3
-5
-10
+1
+10
+30
-5
calls: 7 sum: 13 deepest dip: -17 this route needs: 8
knight
3x3
knight
princess
-2
-3
+3
-5
-10
+1
+10
+30
-5
calls: 9 sum: -16 deepest dip: -17 this route needs: 18
knight
3x3
knight
princess
-2
-3
+3
-5
-10
+1
+10
+30
-5
calls: 11 sum: -5 deepest dip: -5 this route needs: 22
knight
3x3
knight
princess
-2
-3
+3
-5
-10
+1
+10
+30
-5
calls: 13 sum: 15 deepest dip: -15 this route needs: 22
knight
3x3
knight
princess
-2
-3
+3
-5
-10
+1
+10
+30
-5
calls: 16 sum: -19 deepest dip: -19 this route needs: 16
knight
3x3
knight
princess
-2
-3
+3
-5
-10
+1
+10
+30
-5
calls: 18 sum: -1 deepest dip: -5 this route needs: 20
knight
3x3
knight
princess
-2
5
-3
2
+3
5
-5
-10
+1
6
+10
+30
-5
1
calls: 19 sum: -6 deepest dip: -6 this route needs: 7
minimum starting HP =
7
algo
master
.
io
Step:
A knight walks right/down to the princess. Find the smallest starting HP that keeps HP >= 1 the whole way
0 / 73
Input
Example 1
Single Cell
Example 3
2x2 All Negative
2x3 Mixed
Custom
dungeon
=
[-2,-3,3], [-5,-10,1], [10,30,-5]
0 / 73
algo
master
.
io
Step:
A knight walks right/down to the princess. Find the smallest starting HP that keeps HP >= 1 the whole way
