Add Solution Comment

applewjg · applewjg · commit c859933acfec · 2015-01-07T00:38:44.000+08:00
Change-Id: Ifc2f55e3a3f0526509fc73ff908cb59d28d307b2
diff --git a/DungeonGame.h b/DungeonGame.h
@@ -27,7 +27,25 @@
  The knight's health has no upper bound.
  Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.
 
- Solution: ...
+ Solution: 
+ Fortunately, this problem can be solved through a table-filling Dynamic Programming technique, similar to other "grid walking" problems:
+
+To begin with, we should maintain a 2D array D of the same size as the dungeon, where D[i][j] represents the minimum health that guarantees the survival of the knight for the rest of his quest BEFORE entering room(i, j). Obviously D[0][0] is the final answer we are after. Hence, for this problem, we need to fill the table from the bottom right corner to left top.
+
+Then, let us decide what the health should be at least when leaving room (i, j). There are only two paths to choose from at this point: (i+1, j) and (i, j+1). Of course we will choose the room that has the smaller D value, or in other words, the knight can finish the rest of his journey with a smaller initial health. Therefore we have:
+
+  min_HP_on_exit = min(D[i+1][j], D[i][j+1])
+Now D[i][j] can be computed from dungeon[i][j] and min_HP_on_exit based on one of the following situations:
+
+If dungeon[i][j] == 0, then nothing happens in this room; the knight can leave the room with the same health he enters the room with, i.e. D[i][j] = min_HP_on_exit.
+If dungeon[i][j] < 0, then the knight must have a health greater than min_HP_on_exit before entering (i, j) in order to compensate for the health lost in this room. The minimum amount of compensation is "-dungeon[i][j]", so we have D[i][j] = min_HP_on_exit - dungeon[i][j].
+If dungeon[i][j] > 0, then the knight could enter (i, j) with a health as little as min_HP_on_exit - dungeon[i][j], since he could gain "dungeon[i][j]" health in this room. However, the value of min_HP_on_exit - dungeon[i][j] might drop to 0 or below in this situation. When this happens, we must clip the value to 1 in order to make sure D[i][j] stays positive: D[i][j] = max(min_HP_on_exit - dungeon[i][j], 1).
+Notice that the equation for dungeon[i][j] > 0 actually covers the other two situations. We can thus describe all three situations with one common equation, i.e.:
+
+D[i][j] = max(min_HP_on_exit - dungeon[i][j], 1)
+for any value of dungeon[i][j].
+
+Take D[0][0] and we are good to go. Also, like many other "table-filling" problems, the 2D array D can be replaced with a 1D "rolling" array here.
  */
 class Solution {
 public:
