Dungeon Game
The demons had captured the princess and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of m x n rooms. Our valiant knight was initially positioned in the top-left room and must fight through the dungeon to rescue the princess. The knight has an initial health point. Some rooms have demons that decrease health, others have magic orbs that increase health. Determine the minimum initial health needed so the knight can rescue the princess.
Dungeon Game

The demons had captured the princess and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of m x n rooms. Our valiant knight was initially positioned in the top-left room and must fight through the dungeon to rescue the princess. The knight has an initial health point. Some rooms have demons that decrease health, others have magic orbs that increase health. Determine the minimum initial health needed so the knight can rescue the princess.

Example 1:
Input: [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output: 7
Input
arr =[[-2,-3,3],[-5,-10,1],[10,30,-5]]

Initialize DP table. Work backwards from princess (bottom-right).

Dungeon (health changes)
-2
K
-3
+3
-5
-10
+1
+10
+30
-5
P
DP (min HP needed to reach end)
-
-
-
-
-
-
-
-
-
Variables
No variables to display
DepthFunction Call
Stack empty
0/10