This question was asked in an company coding round which unfortunately I was unable to solve, I am getting the glimpse that this question is based on greedy but cannot proceed further, anyone who has solution or algorithm please share it with me.

Problem Statement:

Mustafa wants to cross a dungeon. The dungeon has N cells, and in every cell, there are M monsters. To cross each cell he has to kill one monster, on killing the monster, he loses the strength equal to that of the monster and gains some confidence which adds up to his strength and he proceeds to the next cell. Mustafa can only kill a monster if his strength is greater than or equal to the strength of the monster. Help him find the minimum strength he must have in the beginning so that he can cross N cells.

Input format:

• First two integers are N and M.
• N X M matrix that represents energy required to kill monster in each cell.
• N X M matrix that represents confidence gain by killing respective monsters.

Testcase:

Input:

3 3
3 2 5
8 9 1
4 7 6
1 1 1
1 1 1
1 1 1

Output:

5

Can this question be solved using Dynamic programming?

CodePudding user response：

Let us call Energy[N][M]) the energy needed to kill each monster, and Conf[N][M]the associated confidence.

Let us call Stren[N]the minimum energy that you will need to pass each cell.

We need to select the good monster at each step. The issue is that at first cell for example, you cannot make the good decision without considering all the next cells. A DP solution or a DFS one will certainly work. However, the complexity would be quite high.

The hint to use a greedy solution is correct, at the condition to start from the end.

At the last cell, the needed strength is easily calculated:

​ Strength[n-1] = min_i Energy[n-1][i]

The next strengths are then iteratively calculated, from back to the top:

​ Strength[j] = min_i (Energy[j][i], Energy[j][i] - Conf[j][i] Strength[j 1]) For all j

Final result: Strength[0]

Complexity: linear O(NM). Impossible to do better as you have to consider each monster.

Some further explanations

Performing an iteration in reverse order is a classical trick, when you know the starting value, here Strength[N-1].

The key point is the recursive formula:

  Strength[j] = min_i (Energy[j][i], Energy[j][i] - Conf[j][i]   Strength[j 1])
 

This is the formula that one would apply with DP too, for example. Where does it come from?

For Cell j, the strength Strength[j] must fulfill two constraints.

1. You needed to kill one monster in the current Cell. Therefore, if monster i is selected, the the strength must verify

   Strength[j][i] >= Energy[j][i]
   

2. After filling monster i, you need to keep enough strength, so that the remaining strength is higher that Strength[j ], in order to pass the next cells.

   Remaining strength = Strength[j][i] - Energy[j][i]   Conf[j][i] >= Strength[j 1]
   

So, if monster i is selected, the minimum strength you must have, according to this criteria, is

  Strength[j][i] = Energy[j][i] - Conf[j][i]   Strength[j 1]

Having these two constraints for each monster i, then you can select the best one by minimizing the maximum of these two thresholds.