Day 21 of 30 days/JUNE CHALLENGE/LEETCODE/
The demons had captured the princess (P) and imprisoned her in the bottom-right 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 top-left 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.
DP APPROACH:
Since its a dp question(Obvious) lets just start by defining the meaning of a cell,
so a cell of dp here means how many more points do I need after I have collected points of current cell to reach my target.
explaination:-
We have this dungeon values and lets start by filling values at bottom right, (the smallest problem in dp), now as I reach the bottom right cell, I have -5 points since at last cell I want to be at 1 points (atleast) I should have at least 6 points at the time of landing bottom right cell so that as soon as I enter in the bottom right cell i loose my -5 points(due to current cell value) and I would be at 1 poin, which is what we want.
Now lets aim at the next point (i.e, X) since as soon as I enter that cell I would get 1 point and I need 6 points to reach the bottom(via my next cell) I should have at least 5 points at current such that when I enter current cell I would have 6 point atleast and I can go to next cell (i.e, downwards).
Now lets target the next X value in dp table, As soon as I enter that cell I gain 30 points and I need only 6 points from that position to reach the end so If i come without any point (i.e, 0 value) still I sould gain 30 points and would reach end but since to keep alive I need atleast 1 point so I would fill it with 1.
Now lets see another interesting position,
here I have two choices either go via left side or bottom side since bottom side is cheaper and require least health so I would prefer to going from that side. Now as soon as I reach this cell I have -10 value so I should have atleast 11 points before entering it such that after entering I become 1 point which is needed to go via bottom side.
So the recursive formula is :-
i.e, find the least health requiring path, see how much you need, If you need less than or equals to 0 it means you need no health at this cell at all, but to be alive you need atleast 1 health, otherwise you need what you need.
