"Dungeon Game" solution
Dynamic programming solution

This problem can be solved with a dynamic programming solution by starting at the end cell and working upwards and leftwards to the starting cell.  The basic premise is:


You need to construct a new matrix of values which holds the minimum health required to have before reaching a square.  For example, if m[5][3] is 10, it means that you need 10 health to reach the finish, if you were at (4,3) or (5,2) and were about to move to (5,3).
Start with the end cell, and set its value to max(1, 1 - dungeon[lastcell]).
Then working your way upwards and leftwards, you can set each cell like this:

downHealth  = max(1, m[downNeighbor ] - d[thiscell]);
rightHealth = max(1, m[rightNeighbor] - d[thiscell]);
m[thiscell] = min(downHealth, rightHealth);


Note that some cells do not have both neighbors, so you just set the value to the health computed for the neighbor that exists.