Dungeon Game@LeetCode
文章目录
Dungeon Game
典型的动态规划题。维护一个二维数组dungeon,dungeon[i][j]表示从第i行第j出发到终点所需要的最低血量(包含当前位置的消耗),最低血量不大于1。
递推公式为:
dungeon[i][j] = Math.max(1, -dungeon[i][j] + Math.min(dungeon[i + 1][j], dungeon[i][j + 1]));
实现代码:
javapublic 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]; } }

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论