Problem
The demons had captured the princess (P) and imprisoned her in the
bottomright corner of a dungeon. The dungeon consists of M x N rooms
laid out in a 2D grid. Our valiant knight (K) was initially positioned
in the topleft room and must fight his way through the dungeon to
rescue the princess.The knight has an initial health point represented by a positive
integer. If at any point his health point drops to 0 or below, he dies
immediately.Some of the rooms are guarded by demons, so the knight loses health
(negative integers) upon entering these rooms; other rooms are either
empty (0’s) or contain magic orbs that increase the knight’s health
(positive integers).In order to reach the princess as quickly as possible, the knight
decides to move only rightward or downward in each step.Write a function to determine the knight’s minimum initial health so
that he is able to rescue the princess.For example, given the dungeon below, the initial health of the knight
must be at least 7 if he follows the optimal pathRIGHT> RIGHT >
.
DOWN > DOWNNotes:
 The knight’s health has no upper bound.
 Any room can contain threats
or powerups, even the first room the knight enters and the
bottomright room where the princess is imprisoned.
I was tackling this problem and I ended up with code that is functional, but times out with really large input (meaning it’s poorly optimized). I’m a beginner in programming and working out a functional algorithm was extremely hard for me. Now that I have to optimize it, I don’t even know how to start.
Is there a way to optimize this code that doesn’t change the fundamental underlying logic or is the approach I took doomed to be inefficient? If there is a way to optimize this, could you please provide some examples?
class Solution {
public:
int calculateMinimumHP(vector< vector<int> > &dungeon) {
return 1  actualFunction(dungeon, 0, 0, 0);
}
int actualFunction(vector< vector<int> > &dungeon, int roomCoordX, int roomCoordY, int shield){
if(dungeon.size() == roomCoordX + 1 && dungeon[0].size() == roomCoordY + 1){
if(shield + dungeon[roomCoordX][roomCoordY] < 0)
return (dungeon[roomCoordX][roomCoordY] + shield);
else
return (0);
}
if(dungeon.size() == roomCoordX + 1){
if(shield + dungeon[roomCoordX][roomCoordY] < 0)
return (dungeon[roomCoordX][roomCoordY] + shield) + actualFunction(dungeon, roomCoordX, roomCoordY + 1, 0);
else
return 0 + actualFunction(dungeon, roomCoordX, roomCoordY + 1, dungeon[roomCoordX][roomCoordY] + shield);
}
if(dungeon[0].size() == roomCoordY + 1){
if(shield + dungeon[roomCoordX][roomCoordY] < 0)
return (dungeon[roomCoordX][roomCoordY] + shield) + actualFunction(dungeon, roomCoordX + 1, roomCoordY, 0);
else
return 0 + actualFunction(dungeon, roomCoordX + 1, roomCoordY, dungeon[roomCoordX][roomCoordY] + shield);
}
int temp1;
int temp2;
if(shield + dungeon[roomCoordX][roomCoordY] < 0){
temp1 = actualFunction(dungeon, roomCoordX + 1, roomCoordY, 0);
temp2 = actualFunction(dungeon, roomCoordX, roomCoordY + 1, 0);
return(shield + dungeon[roomCoordX][roomCoordY]) + ((temp1 > temp2) ? temp1 : temp2);
}
else{
temp1 = actualFunction(dungeon, roomCoordX + 1, roomCoordY, dungeon[roomCoordX][roomCoordY] + shield);
temp2 = actualFunction(dungeon, roomCoordX, roomCoordY + 1, dungeon[roomCoordX][roomCoordY] + shield);
return 0 + ((temp1 > temp2) ? temp1 : temp2);
}
}
};
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.