# Day 23: 174. Dungeon Game

## Tag:每月挑戰(2021.10.02)

### Source:
https://leetcode.com/problems/dungeon-game/
### 1.題意:
#### 故事:
王子救公主，過程中會經過打鬥(扣血HP--)，或是補能量(HP++)。
王子從最左上移動到最右下(公主位)，條件是不管在哪一格**血量最少為1**。

### 2.思路:
#### 作法:
從(0,0)位置開始，有向右的路，有向下的路，
可以往右走，也就是先考慮(0,0)右邊那一格一開始最少需多少HP;
也可以往左走，也就是先考慮(0,0)左邊那一格一開始最少需多少HP;
知道往右往下的最小HP後，選擇較少的那一個方向+原先那個位置(ex:0,0)的
HP(`right/down-dungeon[x][y]`)。

**Example:**

[-5 -3]
[ 0  0]
往右走需4: 4-3=1
往下走需1: 1-0=1
考慮原本出發點(0,0)，選往下走的1-(-5)=6
但是... 還有其他Case需考慮

再改寫HP(`right/down-dungeon[x][y]`) for all cases!

[5,-3]
[0, 0]
如果套入 (right/down)-dungeon[x][y]，則
1-5 = (-4) # 補血過頭
因此 那一格(0,0)最少血量數為1，改寫為
max(1,(right/down)-dungeon[x][y]) = max(1,(-4)) = 1

也同時適用於

[1,-3]
[0, 0]
1-1 = 0
如果一開始血量為0，則HP不夠，所以依舊套用 max(1,(right/down)-dungeon[x][y])

再來就是考慮**邊界條件**
1. 最右下那一格

- Case1: `1-dugeon[x][y]`

    [-1] #1-(-1)=2

- Case2: max(1,1-dugeon[x][y])

    [1] #1-1=0

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

- 同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
#### Result:

#### Level:`Hard`

#### 參考

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