[leetcode] Dungeon Game

想了半天 没想到和binary search有什么关系 点了下tag发现是dp那就很简单了
bottom up, 算出沿路negative的最小值...
具体逻辑看code吧。。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

public class Solution { public int calculateMinimumHP(int[][] dungeon) { if (dungeon == null || dungeon.length < 1 || dungeon[0].length < 1){ return 0; } int rowLen = dungeon.length; int columnLen = dungeon[0].length; int lastRow = rowLen-1; int lastColumn = columnLen-1; int dun[] = new int[columnLen]; dun[lastColumn] = dungeon[lastRow][lastColumn] <= 0? dungeon[lastRow][lastColumn]:0; for (int i = lastColumn-1; i >= 0; i--){ dun[i] = dun[i+1]+dungeon[lastRow][i] <= 0? dun[i+1]+dungeon[lastRow][i]:0; } for (int i = dungeon.length-2; i >= 0; i--){ dun[lastColumn] = dungeon[i][lastColumn] + dun[lastColumn] <= 0?dungeon[i][lastColumn] + dun[lastColumn]:0; for (int j = lastColumn-1; j >= 0; j--){ int goRight = dun[j+1]+dungeon[i][j]; int goDown = dun[j]+dungeon[i][j]; if (Math.max(goRight, goDown) > 0){ dun[j] = 0; }else{ dun[j] = Math.max(goRight, goDown); } } } return Math.abs(dun[0])+1; } }