Find the minimum strength someone must have in the beginning so that he can cross N cells Interview question

Question

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 represents the energy required to kill the monster in each cell.
• N X M matrix that represents confidence gained 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 someone tell me I can solve this with  Dynamic programming?

Answer 1

Energy[N][M]) - The energy needed to kill each monster.

Conf[N][M] - The associated confidence.

Stren[N] - The minimum energy that you will need to pass each cell.

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]

The key point is the recursive formula:

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

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

• You have to kill one of the monster in the current Cell.

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

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

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

After this, you can select the best one by minimizing the maximum of these two thresholds.

I hope this helps.

Answer 2

#include <bits/stdc++.h>

using namespace std;

int main()

{

    vector<vector<int>>energy, confi;

    energy = {{3, 2, 5}, {8, 9, 1}, {4, 7, 6}};

    confi = {{1, 1, 1}, {1, 1, 1}, {1, 1, 1}};

   

    int n = 3; // no. of rows

    int m  = 3; // no. of columns

   

    int strength = INT_MAX;

   

    // calculate the min energy from the last row

    for(int i=0; i<m; i++)

         strength = min(strength, energy[n-1][i]);

   

    // start from the last second row

    for(int i = n-2; i>=0; i--){

        int temp_min = INT_MAX;

        for(int j = 0; j<m; j++){

            temp_min = min(temp_min, energy[i][j] - confi[i][j] + strength);

        }

        strength = temp_min;

    }

    cout<<strength;

    return 0;

}

Answer 3

class Solution {
public:
    int calculateMinimumHP(vector<vector<int>>& grid) {
        
        int n = grid.size();
        
        int m = grid[0].size();
        
        // declare a dp
        
        vector<vector<int>> dp(n, vector<int> (m, 0));
        
        // fill the dp table
        
        // dp[i][j] will store the minimum initial energy required from (i, j) to (n - 1, m - 1)
        
        for(int i = n - 1; i >= 0; i--)
        {
            for(int j = m - 1; j >= 0; j--)
            {
                if(i == n - 1 && j == m - 1)
                {
                    dp[i][j] = grid[i][j] >= 0 ? 0 : grid[i][j];
                }
                else if(j == m - 1)
                {
                    dp[i][j] = grid[i][j] + dp[i + 1][j] >= 0 ? 0 : (grid[i][j] + dp[i + 1][j]);
                }
                else if(i == n - 1)
                {
                    dp[i][j] = grid[i][j] + dp[i][j + 1] >= 0 ? 0 : (grid[i][j] + dp[i][j + 1]);
                }
                else
                {
                    int right = grid[i][j] + dp[i][j + 1] >= 0 ? 0 : (grid[i][j] + dp[i][j + 1]);
                    
                    int down = grid[i][j] + dp[i + 1][j] >= 0 ? 0 : (grid[i][j] + dp[i + 1][j]);
                    
                    dp[i][j] = max(right, down);
                }
            }
        }
        
        return -dp[0][0] + 1;
    }
};