Make the best out of this problem


#1

This problem is a good learning experience. I suggest that you first write your solution, try to submit it. If it gives WA print out the entire dp array and figure out exactly why it doesn’t work. You won’t appreciate the original solution as much if you reveal it right away.


#2

If you are thinking
Why Top Down Approach won’t/doesn’t work:
If you solve this problem with top down, then optimal sub-substructute property of this problem would break for DP. Only bottom up approach devises substructure property.
This problem is not same in reverse. Here, ordering/direction matters.


#3

Lol. did you solve the question or not?
If there is a bottom up approach then there’s always a top down approach and vice-versa.
If bottom up satisfies optimal sub-substructure property then top down also satisfies that.
Get your basics straight. But top down will give Memory limit exceeded due to recursion stack overflow.
And you are right about direction though. We can’t calculate from top left to bottom right rather we need to do it from bottom right to top left.


#4

// Top Down Approach
int Solution::calculateMinimumHP(vector<vector > &A) {
int row=A.size(),col=A[0].size(),i,j;
if(row==1 && col==1)
{
if(A[0][0]>0)
return 1;
return abs(A[0][0])+1;
}
vector<vector<pair<int,int>>>dp(row,vector<pair<int,int>>(col,{0,0}));
if(A[0][0]<0)
dp[0][0] = {A[0][0],A[0][0]};
else
dp[0][0] ={A[0][0],0};
for(i=1;i<row;++i)
{
dp[i][0].first+=A[i][0]+dp[i-1][0].first;
dp[i][0].second=min(dp[i][0].first,dp[i-1][0].second);
}
for(j=1;j<col;++j)
{
dp[0][j].first+= A[0][j]+dp[0][j-1].first;
dp[0][j].second=min(dp[0][j].first,dp[0][j-1].second);
}
for(i=1;i<row;++i)
{
for(j=1;j<col;++j)
{
dp[i][j].first=A[i][j]+max(dp[i-1][j].first,dp[i][j-1].first);

            dp[i][j].second = max( min(dp[i-1][j].second,dp[i-1][j].first+A[i][j]),
                  min(dp[i][j-1].second,dp[i][j-1].first+A[i][j]) ); 
    }
}
    // print(dp);
    if(dp[row-1][col-1].second>0) return 1;
return abs(dp[row-1][col-1].second)+1;

}


#5

Hi Shivam, I did almost same approach like yours, but I am getting WA for some corner cases, can you pls check it.

int Solution::calculateMinimumHP(vector<vector<int> > &A) {
    int n = A.size();
    int m = A[0].size();
    vector<vector<pair<int,int>>> dp(n,vector<pair<int,int>>(m,make_pair(0,0)));
    dp[0][0] = {A[0][0],A[0][0]};
    for(int i =1;i<n;i++)
    {
        dp[i][0] = {min(dp[i-1][0].second + A[i][0],dp[i-1][0].first),dp[i-1][0].second+A[i][0]};
    }
    for(int j =1;j<m;j++)
    {
        dp[0][j] = {min(dp[0][j-1].second + A[0][j],dp[0][j-1].first),dp[0][j-1].second+A[0][j]};
    }
    
    for(int i =1;i<n;i++)
    {
        for(int j=1;j<m;j++)
        {
            if((dp[i-1][j].first < dp[i][j-1].first) || (dp[i-1][j].first == dp[i][j-1].first && dp[i-1][j].second > dp[i][j-1].second) )
            {
                dp[i][j] = {min(dp[i][j-1].second + A[i][j],dp[i][j-1].first),dp[i][j-1].second+A[i][j]};
            }
            else
            {
                dp[i][j] = {min(dp[i-1][j].second + A[i][j],dp[i-1][j].first),dp[i-1][j].second+A[i][j]};
            }
        }
    }
    return dp[n-1][m-1].first>=0?0:abs(dp[n-1][m-1].first)+1;
}


#6

There you go, a Recursive Top Down Approach, works flawlessly. Really nice problem i’d say. Seems easy at first, but is decently challenging.

vector<vector<int>>a,DP;
int n,m;
int dp(int i,int j){
    if(i>=n||j>=m)return INT_MIN/20;
    if(i==n-1&&j==m-1)return a[i][j];
    if(DP[i][j]!=-1)return DP[i][j];
    int x=dp(i+1,j);
    int y=dp(i,j+1);
    return DP[i][j]=min(a[i][j],a[i][j]+max(x,y));
}


int Solution::calculateMinimumHP(vector<vector<int> > &A) {
    a=A;
    n=a.size();m=a[0].size();
    DP.clear();
    DP.resize(n,vector<int>(m,-1));
    int mx=dp(0,0);
    if(mx>0)mx=1;
    else mx=1-mx;
    return mx;
}