Knight on the Unique Paths II

Same problem as Unique Paths II. Only different is to walk from end to start.

The Dungeon

+-----+-----+-----+
| -2  | -3  |  3  |  A
+-----+-----+-----+
| -5  | -10 |  1  |  B
+-----+-----+-----+
| 10  | 30  | -5  |  C
+-----+-----+-----+

   1     2     3

The minimum health when the Knight reach the final Boss

Let make a table.

final room need 1 - (-5) = 6 HP (hp - 5 = 1 to survive)

+-----+-----+-----+
|     |     |     |  A
+-----+-----+-----+
|     |     |     |  B
+-----+-----+-----+
|     |     |  6  |  C
+-----+-----+-----+

   1     2     3

the Knight can enter the final room from either C2 or B3.

in C2 he can got 30 HP, so if he could reach C2 then he can enter the final room. So he only need to survive (1 HP). 1 + 30 > 6.

in B3 he will get 1 HP. the Knight will need 5 (6 - 1) HP to reach the final room.

+-----+-----+-----+ 
|     |     |     |  A
+-----+-----+-----+
|     |     |  5  |  B
+-----+-----+-----+
|     |  1  |  6  |  C
+-----+-----+-----+

   1     2     3

in B2, the Knigth need 11 (1 - (-10)) HP to reach C2 and 15 (5 - (-10)) to reachB3`.

If I were the Knight i would enter C2 because it requires less HP. B2 = MIN(11, 15)

+-----+-----+-----+ 
|     |     |     |  A
+-----+-----+-----+
|     | 11  |  5  |  B
+-----+-----+-----+
|     |  1  |  6  |  C
+-----+-----+-----+

   1     2     3

In gerneral, HPNeed[x][y] = MIN(HPNeed[x + 1][y] - D[x][y], HPNeed[x][y + 1] - D[x][y]).

Sometimes, the HPNeed[x][y] might go below zero, like C2 <- C3, that means 1 HP is OK.

The work is to fill up the table, and the first cell is the answer.

+-----+-----+-----+ 
|  7  |  5  |  2  |  A
+-----+-----+-----+
|  6  | 11  |  5  |  B
+-----+-----+-----+
|  1  |  1  |  6  |  C
+-----+-----+-----+

   1     2     3