DAY 23
0

# Day 23: 174. Dungeon Game

## Tag:每月挑戰(2021.10.02)

### Source:

https://leetcode.com/problems/dungeon-game/

### 2.思路:

#### 作法:

HP(`right/down-dungeon[x][y]`)。

Example:

``````[-5 -3]
[ 0  0]

``````

``````[5,-3]
[0, 0]

1-5 = (-4) # 補血過頭

max(1,(right/down)-dungeon[x][y]) = max(1,(-4)) = 1
``````

``````[1,-3]
[0, 0]
1-1 = 0

``````

1. 最右下那一格
• Case1: `1-dugeon[x][y]`

``````[-1] #1-(-1)=2
``````
• Case2: max(1,1-dugeon[x][y])

``````[1] #1-1=0
``````
1. 走到最右邊，只能往下走

• 同max(1,(right/down)-dungeon[x][y])概念
• 但由其下面的那一格推來，所以`x+1,y`-dungeon[x][y]
2. 走到最下面，只能往右走

• 同max(1,(right/down)-dungeon[x][y])概念
• 但由其右邊的那一格推來，所以`x,y+1`-dungeon[x][y]

#### 註解幫助理解程式(作法<->Code)

``````to be continue ...
``````

#### 過程: recursive -> recursive+cache(不重複計算) -> iterative(再加快)

##### What happened to recursive?
• Why need more time??

### 3.程式碼:

#### v1-TLE(recursive without cache)

``````def calculateMinimumHP(dungeon,x,y):
m = len(dungeon) # row
n = len(dungeon[0]) # col
if x == (m-1) and y == (n-1):
return max(1,1-dungeon[x][y])
if x == (m-1):
return max(1,calculateMinimumHP(dungeon,x,y+1)-dungeon[x][y])
if y == (n-1):
return max(1,calculateMinimumHP(dungeon,x+1,y)-dungeon[x][y])
# 計算從(0,0)右邊那一格一開始的最小血量
right = calculateMinimumHP(dungeon,x+1,y)
down  = calculateMinimumHP(dungeon,x,y+1)
if right < down:
return max(1,right-dungeon[x][y])
else:
return max(1,down-dungeon[x][y])

class Solution:
def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
return calculateMinimumHP(dungeon,0,0)
``````

#### v2-(recursive with cache)

``````def calculateMinimumHP(dungeon,x,y,cache):
m = len(dungeon) # row
n = len(dungeon[0]) # col
if x == (m-1) and y == (n-1):
return max(1,1-dungeon[x][y])
if x == (m-1):
return max(1,calculateMinimumHP(dungeon,x,y+1,cache)-dungeon[x][y])
if y == (n-1):
return max(1,calculateMinimumHP(dungeon,x+1,y,cache)-dungeon[x][y])
# 計算從(0,0)右邊那一格一開始的最小血量
if (x,y) in cache:
return cache[x,y]

right = calculateMinimumHP(dungeon,x+1,y,cache)
down  = calculateMinimumHP(dungeon,x,y+1,cache)
if right < down:
cache[x,y] = max(1,right-dungeon[x][y])
else:
cache[x,y] = max(1,down-dungeon[x][y])
return cache[x,y]
class Solution:
def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
return calculateMinimumHP(dungeon,0,0,{})
``````

#### v3-iterative

``````def calculateMinimumHP(dungeon):
m = len(dungeon) # row
n = len(dungeon[0]) # col
cache = {}
for x in reversed(range(0,m)):
for y in reversed(range(0,n)):

if x == (m-1) and y == (n-1):
cache[x,y] = max(1,1-dungeon[x][y])
elif x == (m-1):
cache[x,y] = max(1,cache[x,y+1]-dungeon[x][y]) # 碰最後一列，所以只能右移
elif y== (n-1):
cache[x,y] = max(1,cache[x+1,y]-dungeon[x][y]) # 碰最後一行，所以只能下移
else:
right = cache[x+1,y]
down  = cache[x,y+1]
if right < down:
cache[x,y] = max(1,right-dungeon[x][y])
else:
cache[x,y] = max(1,down-dungeon[x][y])
return cache[0,0]
class Solution:
def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
return calculateMinimumHP(dungeon)
``````

PS: reversed(range(0,m)), reversed(range(0,n))

• reversed(range(0,m)): m-1~0
• reversed(range(0,n)): n-1~0

#### 參考

https://youtu.be/--2fhxZcWPo

FRIENDS30