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
