//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.
//
//For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.
//
//-2 (K)	-3	    3
//-5	    -10	    1
//10	    30	    -5 (P)
//
//Notes:
//
//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.
package org.leituo.leetcode.dpHard;

/**
 * Created by leituo56 on 1/23/15.
 */
public class DungeonGame {
    class Solution{
        public int calculateMinimumHP(int[][] dungeon) {
            int rowL = dungeon.length;
            int colL = dungeon[0].length;
            int[][] hp = new int[rowL+1][colL+1];//min hp need before step on i, j point.
            for(int i=0; i<=rowL;i++)
                for(int j=0; j<=colL;j++)
                    hp[i][j] = Integer.MAX_VALUE;//like a wall
            hp[rowL][colL-1] = 1;//remian at least 1 health
            hp[rowL-1][colL] = 1;
            for(int row = rowL-1; row >=0 ; row--){
                for(int col = colL-1; col >=0; col--){
                    int needed = Math.min(hp[row+1][col], hp[row][col+1]) - dungeon[row][col];
                    hp[row][col] = needed <= 0? 1 : needed;
                }
            }
            return hp[0][0];
        }
    }
}

@@ -1457,23 +1457,309 @@
     
-class Solution%7B
+//%E8%BF%B7%E5%AE%AB%EF%BC%8C%E6%AF%8F%E4%B8%AA%E6%88%BF%E9%97%B4%E5%8A%A0%E8%A1%80%E6%88%96%E8%80%85%E6%8E%89%E8%A1%80%EF%BC%8C%E6%B1%82%E5%B7%A6%E4%B8%8A%E5%88%B0%E5%8F%B3%E4%B8%8B%E9%9C%80%E8%A6%81%E7%9A%84%E6%9C%80%E5%B0%91%E7%94%9F%E5%91%BD%E5%80%BC%0A    class Solution%7B%0A        //Think reverse%0A        //extra memory to handle HP needed to finish dungeon%0A        //loop reversely, last one need 1 HP,%0A        //each room choose right or bottom, always choose the easy one(min)%0A        //if cur HP needed is %3C=0, set to 1
 %0A   
@@ -2506,32 +2506,32 @@
 %7D%0A            %7D%0A
-
             retu
@@ -2559,10 +2559,983 @@
 %7D%0A    %7D%0A
+    class SolutionLessRAM %7B%0A        //Same idea, use sliding window to use less memory%0A        public int calculateMinimumHP(int%5B%5D%5B%5D dungeon) %7B%0A            if(dungeon == null %7C%7C dungeon.length %3C 1 %7C%7C dungeon%5B0%5D.length %3C 1)%0A                return 1;%0A            int rows = dungeon.length;%0A            int cols = dungeon%5B0%5D.length;%0A            int%5B%5D data = new int%5Bcols + 1%5D;//extra dummy, for easy if/else handling%0A            for(int k = 0; k %3C cols - 1; k++)%0A                data%5Bk%5D = Integer.MAX_VALUE;//set wall%0A            data%5Bcols%5D = data%5Bcols-1%5D = 1;//extra dummy%0A            for(int i = rows - 1; i %3E= 0; i--)%7B%0A                for(int j = cols - 1; j %3E= 0; j--)%7B%0A                    int needHP = Math.min(data%5Bj%5D, data%5Bj+1%5D) - dungeon%5Bi%5D%5Bj%5D;//always choose the easy path%0A                    data%5Bj%5D = needHP %3C 1 ? 1 : needHP;%0A                %7D%0A                data%5Bcols%5D = Integer.MAX_VALUE;//set back wall%0A            %7D%0A            return data%5B0%5D;%0A        %7D%0A    %7D%0A
 %7D%0A

comment dungeon game