Question

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.

Answer 1

The minimum strength he must have in the beginning so that he can cross n cells is gotten from; Strength[n - 1] = min_i Energy[n-1] [i]

How to create an Algorithm?

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.

Thus using a greedy solution at the condition to start from the end would be the best thing to do.

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.

Read more about Creating Algorithms at; brainly.com/question/13800096

#SPJ1