「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);
};

經過這次努力，終於通過了性能要求。