Dungeon Game@LeetCode

LeetCode

Word count: 218 / Reading time: 1 min

 2015/05/06   Share

Dungeon Game

典型的动态规划题。维护一个二维数组dungeon，dungeon[i][j]表示从第i行第j出发到终点所需要的最低血量（包含当前位置的消耗），最低血量不大于1。

递推公式为：

1	dungeon[i][j] = Math.max(1, -dungeon[i][j] + Math.min(dungeon[i + 1][j], dungeon[i][j + 1]));

实现代码：

public class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        int rows = dungeon.length, cols = dungeon[0].length;
        dungeon[rows - 1][cols - 1] = Math.max(1, -dungeon[rows - 1][cols - 1] + 1);
        for (int j = cols - 2; j >= 0; j--) {
            dungeon[rows - 1][j] = Math.max(1, -(dungeon[rows - 1][j]) + dungeon[rows - 1][j + 1]);
        }
        for (int i = rows - 2; i >= 0; i--) {
            for (int j = cols - 1; j >= 0; j--) {
                if (j == cols - 1) {
                    dungeon[i][j] = Math.max(1, -(dungeon[i][j]) + dungeon[i + 1][j]);
                } else {
                    dungeon[i][j] = Math.max(1, -dungeon[i][j] + Math.min(dungeon[i + 1][j], dungeon[i][j + 1]));
                }
            }
        }
        return dungeon[0][0];
    }
}

原文作者: findingsea

原文链接: http://findingsea.github.io/2015/05/06/dungeon-game-at-leetcode/

发表日期: May 6th 2015, 10:45:00 am

Next Post

二月份阅读报告
Previous Post

Maximum Gap@LeetCode

CATALOG

1. Dungeon Game

