https://leetcode.com/problems/dungeon-game/
王子救公主,过程中会经过打斗(扣血HP--),或是补能量(HP++)。
王子从最左上移动到最右下(公主位),条件是不管在哪一格血量最少为1。
从(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])
再来就是考虑边界条件
Case1: 1-dugeon[x][y]
[-1] #1-(-1)=2
Case2: max(1,1-dugeon[x][y])
[1] #1-1=0
走到最右边,只能往下走
x+1,y
-dungeon[x][y]走到最下面,只能往右走
x,y+1
-dungeon[x][y]to be continue ...
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)
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,{})
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))
Hard
<<: 爬虫怎麽爬 从零开始的爬虫自学 DAY24 python档案读写open( )
前述 终於来到最後一天! 今天就不写程序了, 带大家认识 lottie , 这也是在工作需求才意外学...
先来说一个小故事: 前一阵子跟朋友聊天,朋友说:「我有个创业的点子,想要研发一个跟露营有关的产品!」...
连续 30 天不中断每天上传一支教学影片,教你如何用 React 加上 Firebase 打造社群...
今日文章目录 前言 参考资料 前言 在 Day25-[React] props 中我们练习用pro...
计算BMI BMIT常用来判断肥胖程度,BMI等於体重(KG)除以身高(M)的平方,「BMI与肥胖等...