「leetcode系列」第二十六期 地下城游戏

不知不觉已经进行到26期了，也算坚持了一段时间了，今天特意选了一道困难题目来和大家一起尝试一下。

题目正文

一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。

有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。

为了尽快到达公主，骑士决定每次只向右或向下移动一步。

编写一个函数来计算确保骑士能够拯救到公主所需的最低初始健康点数。

例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为

-2 (K)-33-5-1011030-5 (P)

说明:

• 骑士的健康点数没有上限。
• 任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。

解题思路

这道题目是典型的动态规划问题。

那么难点就是找出规划关系。

最后我的思路似乎变成了遍历的方式。先尝试做一下。

解答

/**
 * @param {number[][]} dungeon
 * @return {number}
 */
var calculateMinimumHP = function(dungeon) {
 var cache = [];
 function cal(n, m){
 if(cache[n + ":" + m] !== undefined){
 return cache[n + ":" + m];
 }
 if(n===0 && m===0){
 cache[n + ":" + m] = [{h : dungeon[0][0], n : dungeon[0][0]}];
 return cache[n + ":" + m];
 }
 if(n < 0 || m < 0){
 return [];
 }
 var map1 = cal(n, m - 1);
 var map2 = cal(n - 1, m);
 var result = [];
 var now, h;
 for(var i in map1){
 now = map1[i]['n'] + dungeon[n][m];
 h = Math.min(map1[i]['h'], now);
 result.push({n: now, h: h});
 }
 for(var i in map2){
 now = map2[i]['n'] + dungeon[n][m];
 h = Math.min(map2[i]['h'], now);
 result.push({n: now, h: h});
 }
 cache[n + ":" + m] = result;
 return result;
 }
 var n = dungeon.length;
 var m = dungeon[0].length;
 var resultMap = cal(n - 1, m - 1);
 var result = resultMap[0]['h'];
 for(var i in resultMap){
 result = Math.max(result, resultMap[i]['h']);
 }
 return Math.max(1, 1 - result);
};

这个解答在正确性上应该没问题了，但是时间复杂度比较高，没有能通过。按照这个思路进行下优化。

var calculateMinimumHP = function(dungeon) {
 var cache = [];
 function cal(n, m){
 if(cache[n + ":" + m] !== undefined){
 return cache[n + ":" + m];
 }
 if(n===0 && m===0){
 cache[n + ":" + m] = [{h : dungeon[0][0], n : dungeon[0][0]}];
 return cache[n + ":" + m];
 }
 if(n < 0 || m < 0){
 return [];
 }
 var map1 = cal(n, m - 1);
 var map2 = cal(n - 1, m);
 var result = [];
 var now, h;
 for(var i = 0, j = 0; i < map1.length || j < map2.length;){
 if(i===map1.length){
 now = map2[j]['n'] + dungeon[n][m];
 h = Math.min(map2[j]['h'], now);
 j++;
 }else if(j===map2.length){
 now = map1[i]['n'] + dungeon[n][m];
 h = Math.min(map1[i]['h'], now);
 i++;
 }else if(map1[i]['h'] === map2[j]['h']){
 now = Math.max(map1[i]['n'], map2[j]['n']) + dungeon[n][m];
 h = Math.min(map1[i]['h'], now);
 i++;
 j++;
 }else if(map1[i]['h'] > map2[j]['h']){
 now = map1[i]['n'] + dungeon[n][m];
 h = Math.min(map1[i]['h'], now);
 i++;
 }else {
 now = map2[j]['n'] + dungeon[n][m];
 h = Math.min(map2[j]['h'], now);
 j++;
 }
 if(result.length === 0 || now > result[result.length - 1]['n']){
 result.push({n: now, h: h});
 }
 
 }
 cache[n + ":" + m] = result;
 console.log(result)
 return result;
 }
 
 var n = dungeon.length;
 var m = dungeon[0].length;
 var resultMap = cal(n - 1, m - 1);
 var result = resultMap[0]['h'];
 for(var i in resultMap){
 result = Math.max(result, resultMap[i]['h']);
 }
 return Math.max(1, 1 - result);
};

注意，这里使用了

 if(result.length === 0 || now > result[result.length - 1]['n']){
 result.push({n: now, h: h});
 }

进行优化，速度是快了很多，因为很多不必要的项没有重复计算，但速度仍达不到要求。

这边尝试把递归转换成循环。

/**
 * @param {number[][]} dungeon
 * @return {number}
 */
var calculateMinimumHP = function(dungeon) {
 
 var cache = [];
 for(var n = 0; n < dungeon.length; n++){
 for(var m = 0; m  
< dungeon[0].length; m++){
 if(n===0 && m===0){
 cache[n + ":" + m] = [{h : dungeon[0][0], n : dungeon[0][0]}];
 continue;
 }
 var map1 = cache[n + ":" + (m - 1)] || [];
 var map2 = cache[(n - 1) + ":" + m] || [];
 var result = [];
 var now, h;
 for(var i = 0, j = 0; i < map1.length || j < map2.length;){
 if(i===map1.length){
 now = map2[j]['n'] + dungeon[n][m];
 h = Math.min(map2[j]['h'], now);
 j++;
 }else if(j===map2.length){
 now = map1[i]['n'] + dungeon[n][m];
 h = Math.min(map1[i]['h'], now);
 i++;
 }else if(map1[i]['h'] === map2[j]['h']){
 now = Math.max(map1[i]['n'], map2[j]['n']) + dungeon[n][m];
 h = Math.min(map1[i]['h'], now);
 i++;
 j++;
 }else if(map1[i]['h'] > map2[j]['h']){
 now = map1[i]['n'] + dungeon[n][m];
 h = Math.min(map1[i]['h'], now);
 i++;
 }else {
 now = map2[j]['n'] + dungeon[n][m];
 h = Math.min(map2[j]['h'], now);
 j++;
 }
 if(result.length === 0 || now > result[result.length - 1]['n']){
 result.push({n: now, h: h});
 }
 
 }
 cache[n + ":" + m] = result;
 }
 }
 
 var resultMap = cache[(dungeon.length - 1) + ":" + (dungeon[0].length - 1)];
 var result = resultMap[0]['h'];
 for(var i in resultMap){
 result = Math.max(result, resultMap[i]['h']);
 }
 return Math.max(1, 1 - result);
};

经过这次努力，终于通过了性能要求。