# ESCARTST-EDITORIAL

Author , Tester , Editorialist : Jashwanth

medium

DP

# PROBLEM:

we are being asked to find the minimum health required to go from top left of the matrix to bottom right position.

# EXPLANATION:

we make a new matrix ( dp matrix )

and fill it with following rules:

• integer in any index position represents the minimum health required to go

from that index position to the exit with health atleast 1

• numbers in the dp matix equals

``````      max( down , right )  -  current corresponding number
``````
• negative value signifies that the person lacks that amount of health ,

if he had that many health points ,

he could reach the exit alive

• positive value signifies that the next step has a poistive number to increase the health points,

hence we can easily say that health required at that position is just 1 , as the next step is surely a positive number

ie. for positive numbers , we replace it with one

in other words , we use min( 1 , max(down,right)-grid[i][j] )
-following this bottom up approach ,we finally reach dp[0][0] which is the

minimum health at starting point to reach the exit alive

# SOLUTION :

``````#include<time.h>

#include<vector>

#include<stdlib.h>

#include<iostream>

using namespace std;

int calculateMinimumHP(vector<vector<int>>& d) {
vector<int> dp(d.size() + 1, 100000000);
dp[d.size() - 1] = 1;
for (int i = d[0].size() - 1; i >= 0; --i)
for (int j = d.size() - 1; j >= 0; --j)
dp[j] = max(1, min(dp[j + 1], dp[j]) - d[j][i]);
return dp[0];
}
int main()
{
int row,column;
cin>>row>>column;
vector<vector<int>> vec(row);
for(int i = 0; i < row; i++)
{
vec[i] = vector<int>(column);
for(int j = 0; j < column; j++)
cin>>vec[i][j];
}
cout<<calculateMinimumHP(vec);
}``````