Problem statement
Contest source
Author , Tester , Editorialist : Jashwanth
DIFFICULTY:
medium
PREREQUISITES:
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 theminimum health at starting point to reach the exit alive
which is the required answer
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);
}