資訊專欄INFORMATION COLUMN
摘要：為了保證騎士可以最終到達(dá)，我們可以從終點(diǎn)逆向走到起點(diǎn)。為正數(shù)表示是藥水，騎士可以相應(yīng)降低初始血量。為負(fù)數(shù)表明要增加血量來保證存活。用二維空間來表示當(dāng)前位置所需的最小血量，不斷向左上方走直到起點(diǎn)。用來表示當(dāng)前層與下一層。
The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms
laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.
Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0"s) or contain magic orbs that increase the knight"s health (positive integers).
In order to reach the princess as quickly as possible, the knight
decides to move only rightward or downward in each step.
本題為最小路徑。在搜索的時(shí)候，保持最小值至少為1。
為了保證騎士可以最終到達(dá)，我們可以從終點(diǎn)逆向走到起點(diǎn)。每到一個(gè)地方有兩種選擇，向上或者向左。
選擇需要初始血量最小的走法。matrix為正數(shù)表示是藥水，騎士可以相應(yīng)降低初始血量。為負(fù)數(shù)表明要增加血量來保證存活。
用二維空間來表示當(dāng)前位置所需的最小血量，不斷向左上方走直到起點(diǎn)。因?yàn)橐粋€(gè)點(diǎn)只有兩種走法，血量只與右邊和下邊有關(guān)。
我們可以減少空間到O(2n)。用來表示當(dāng)前層與下一層。但是我們是逆向走，在dp[j+1]是已經(jīng)是當(dāng)前層，而dp[j]還停留在下一層未更新。所以我們只需一個(gè)O(n)空間就行了。
time: O(n^2), space: O(n)
public class Solution {
public int calculateMinimumHP(int[][] matrix) {
if(matrix == null || matrix.length == 0) return 0;
int m = matrix.length, n = matrix[0].length;
int[] dp = new int[n+1];
Arrays.fill(dp,Integer.MAX_VALUE);
dp[n-1] = 1;
for(int i=m-1;i>=0;i--) {
for(int j=n-1;j>=0;j--){
dp[j] = Math.max(1 , Math.min(dp[j],dp[j+1]) - matrix[i][j]);
} // dp[j] means go down, dp[j+1] means go right
}
return dp[0];
}
}
time: O(n^2), space: O(n^2)
public class Solution {
public int calculateMinimumHP(int[][] dungeon) {
int m = dungeon.length;
int n = dungeon[0].length;
//init dp table
int[][] h = new int[m][n];
h[m - 1][n - 1] = Math.max(1 - dungeon[m - 1][n - 1], 1);
//init last col
for (int i = m - 2; i >= 0; i--) {
h[i][n - 1] = Math.max(h[i + 1][n - 1] - dungeon[i][n - 1], 1);
}
//init last row
for (int j = n - 2; j >= 0; j--) {
h[m - 1][j] = Math.max(h[m - 1][j + 1] - dungeon[m - 1][j], 1);
}
//calculate dp table
for (int i = m - 2; i >= 0; i--) {
for (int j = n - 2; j >= 0; j--) {
int down = Math.max(h[i + 1][j] - dungeon[i][j], 1);
int right = Math.max(h[i][j + 1] - dungeon[i][j], 1);
h[i][j] = Math.min(right, down);
}
}
return h[0][0];
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/66287.html
摘要：題目解答這一題最重要的是把所剩血量初始化血量走這一步消耗的血量這句話讀懂。那么我們假設(shè)是走完后所剩余的血量肯定是大于等于的。如果想存活下來，最少需要上一步血量，即上一步血量然后分類討論上一步血量的可能性，注意邊界情況的初始化即可。 題目： The demons had captured the princess (P) and imprisoned her in the bottom-...
摘要：動(dòng)態(tài)規(guī)劃復(fù)雜度時(shí)間空間遞歸棧思路騎士向右或者向下走，如果血量小于就死掉了，這會(huì)使得計(jì)算變得很復(fù)雜。假設(shè)表示點(diǎn)和的血量，表示走到和要扣除的血量。最右下角那個(gè)節(jié)點(diǎn)沒有待逆推的節(jié)點(diǎn)，所以我們假設(shè)其逆推節(jié)點(diǎn)的血量為。 Dungeon Game The demons had captured the princess (P) and imprisoned her in the bottom-r...
摘要：腦筋急轉(zhuǎn)彎復(fù)雜度時(shí)間空間思路這題往小說可以追溯到小學(xué)奧數(shù)或者腦筋急轉(zhuǎn)彎的書中，往大說可以深究到博弈論。代碼如果一開始就是的倍數(shù)，你就輸了，因?yàn)閷?duì)方可以用同樣的策略 Nim Game You are playing the following Nim Game with your friend: There is a heap of stones on the table, each ...
摘要：復(fù)雜度思路每次設(shè)置一個(gè)窗口，觀察在這一步下能到達(dá)的最遠(yuǎn)距離，不斷的移動(dòng)這個(gè)窗口。計(jì)數(shù)，需要移動(dòng)幾次，才能覆蓋到末尾的值。 LeetCode[45] Jump Game II Given an array of non-negative integers, you are initially positioned at the first index of the array. Eac...
摘要：題目鏈接題目分析給定一個(gè)字符串?dāng)?shù)組，每一個(gè)字符串有以下形式數(shù)字。直接計(jì)算得分。。代表上一輪分?jǐn)?shù)無效。思路這題沒什么好說的了。用區(qū)分各種情況，進(jìn)行相應(yīng)處理即可。最終代碼若覺得本文章對(duì)你有用，歡迎用愛發(fā)電資助。 682. Baseball Game 題目鏈接 682. Baseball Game 題目分析 給定一個(gè)字符串?dāng)?shù)組，每一個(gè)字符串有以下形式： 數(shù)字。直接計(jì)算得分。 +。代表本輪...
閱讀 2774·2021-09-24 10:34
閱讀 1876·2021-09-22 10:02
閱讀 2265·2021-09-09 09:33
閱讀 1469·2021-08-13 15:02
閱讀 3279·2020-12-03 17:10
閱讀 1193·2019-08-30 15:44
閱讀 2156·2019-08-30 12:58
閱讀 3238·2019-08-26 13:40
