首页 > 代码库 > Leetcode#174 Dungeon Game
Leetcode#174 Dungeon Game
原题地址
典型的地图寻路问题
如何计算当前位置最少需要多少体力呢？无非就是在向下走或向右走两个方案里做出选择罢了。
如果向下走，看看当前位置能提供多少体力（如果是恶魔就是负数，如果是草药就是正数），如果当前位置能够提供的体力比向下走所需要的最小体力还多，那么当前位置只需要1的体力就够了；否则，计算出额外需要多少体力。
如果向右走，同理。
设任意坐标(i, j)处最少需要health[i][j]的体力才能通关，则有如下递推公式：
health[i][j] = min{ dungeon[i][j] >= health[i+1][j] ? 1 : health[i+1][j] - dungeon[i][j], dungeon[i][j] >= health[i][j+1] ? 1 : health[i][j+1] - dungeon[i][j]}
因为递推公式只用到了相邻层，所以可以在编码时压缩成1维数组节省空间。
代码：
1 int calculateMinimumHP(vector<vector<int> > &dungeon) { 2 if (dungeon.empty() || dungeon[0].empty()) return -1; 3 4 int m = dungeon.size(); 5 int n = dungeon[0].size(); 6 vector<int> health(n, 0); 7 8 health[n - 1] = dungeon[m - 1][n - 1] >= 0 ? 1 : 1 - dungeon[m - 1][n - 1]; 9 10 for (int j = n - 2; j >= 0; j--)11 health[j] = dungeon[m - 1][j] >= health[j + 1] ? 1 : health[j + 1] - dungeon[m - 1][j];12 13 for (int i = m - 2; i >= 0; i--) {14 health[n - 1] = dungeon[i][n - 1] >= health[n - 1] ? 1 : health[n - 1] - dungeon[i][n - 1];15 for (int j = n - 2; j >= 0; j--) {16 int right = dungeon[i][j] >= health[j + 1] ? 1 : health[j + 1] - dungeon[i][j];17 int down = dungeon[i][j] >= health[j] ? 1 : health[j] - dungeon[i][j];18 health[j] = min(right, down);19 }20 }21 22 return health[0];23 }
Leetcode#174 Dungeon Game
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。