# Dp solution in c (8msec)

• int max_row;
int max_col;
int * dynamic;

int find_health(int** dungeon, int r, int c) {
int max_health = 0, health = 0, x;

``````if (r == max_row - 1 && c == max_col-1 ) {
return dungeon[r][c];
}
if (r < max_row -1) {
if (dynamic[(r+1)*max_col+c] != 100)
{
max_health = dynamic[(r+1)*max_col+c];

} else {
max_health = find_health(dungeon, r+1, c);
dynamic[(r+1)*max_col+c] = max_health;

}
}

if (c < max_col -1) {
if (dynamic[r*max_col+(c+1)] != 100)  {
health = dynamic[r*max_col+(c+1)];

} else {
health = find_health(dungeon, r, c+1);
dynamic[r*max_col+(c+1)] = health;

}
}

if (c >= max_col-1) {
;
} else if (r >= max_row-1)
max_health = health;
else if (max_health < health) {
max_health = health;
}
x = dungeon[r][c] + (max_health > 0 ? 0 : max_health);

return x;
``````

}

int calculateMinimumHP(int** dungeon, int dungeonRowSize, int dungeonColSize) {
int health = 0, n, i;
max_row = dungeonRowSize;
max_col = dungeonColSize;
n = sizeof(int) * dungeonRowSize * dungeonColSize;
dynamic = malloc(n);
for (i=0;i< (n/sizeof(int)); i++) {
*(dynamic+i) = 100;
}

``````health = find_health(dungeon, 0, 0);

if (health >= 0)
return 1;
return ((health * -1)+1);
``````

}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.