Solution :

This problem is probably towards high medium difficulty level but below the hard level of problems. At one glance, one can conclude that we can solve this problem using the dynamic programming technique and it is correct. The only difficulty is in identifying what value to memoize at each step during the King's journey towards the Princess. So this is how it works. The initial health of the King should be such that, it should be greater than the absolute value of the least negative health the King will suffer due to fighting with demons along a path. If the health of the King never becomes negative along the path, then the initial value of health should be 1.

For example, in the below diagram, if the health of the King drops to -21 (-2 -5 -10+1-5), for the path DOWN -> RIGHT -> RIGHT -> DOWN, then he needs at-least 22 health to start with, if he has to follow this path. But this path is not the optimal one, as he can travel RIGHT -> RIGHT -> DOWN -> DOWN with an initial health of 7, because he will lose 6 health along the journey.

The python code to find the minimum positive health for the King is as follows (using recursion and memoization) :

import collections class Solution(object): def calculate_min_health(self, dungeon, start, cache): if start == (len(dungeon) - 1, len(dungeon[0]) - 1): cache[start] = dungeon[start[0]][start[1]] if dungeon[start[0]][start[1]] < 0 else 0 else: p, q = (start[0] + 1, start[1]), (start[0], start[1] + 1) if p[0] < len(dungeon): if p in cache: a = cache[p] else: a = self.calculate_min_health(dungeon, p, cache) else: a = -float("Inf") if q[1] < len(dungeon[0]): if q in cache: b = cache[q] else: b = self.calculate_min_health(dungeon, q, cache) else: b = -float("Inf") c, d = dungeon[start[0]][start[1]] + a, dungeon[start[0]][start[1]] + b cache[start] = max(c, d) if c < 0 and d < 0 else 0 return cache[start] def calculateMinimumHP(self, dungeon): cache = collections.defaultdict(dict) out = self.calculate_min_health(dungeon, (0,0), cache) return 1 - out

Note the condition :

cache[start] = max(c, d) if c < 0 and d < 0 else 0

What this says that only if the health becomes negative along the path, we should memoize it else we consider it as 0, i.e. no loss in health. We take the max of the two possible directions that the King can travel from a single point, because if both healths are negative and we want to capture the highest of the two negative healths as the solution from that point onwards.

At the end, we compute '1 - out', where 'out' is the highest negative health starting from (0, 0), that the King will face if he goes in any of the two directions (0, 1) or (1, 0).

One can also use |out| + 1, which is same in this case.

Categories: PROBLEM SOLVING

Tags: Dungeon Game, Dynamic Programming, Leetcode, Memoization