# Untitled

unknown
c_cpp
a year ago
1.6 kB
2
Indexable
Never
```class Solution {
public:

pair<long, long> func(int x, int y, vector<vector<int>>& a, vector<vector<pair<long, long>>>& dp) {
if(x < 0 || y < 0)
return pair<long, long>(INT_MIN/3, INT_MIN/3);
if(dp[x][y] != pair<long, long>(INT_MIN/3, INT_MIN/3))
return dp[x][y];
pair<long, long> val1 = func(x, y-1, a, dp);
pair<long, long> val2 = func(x-1, y, a, dp);

long pathLenFrom1 = val1.first + a[x][y];
long pathLenFrom2 = val2.first + a[x][y];
long minValIfComingFromPath1 = min(val1.second, pathLenFrom1);
long minValIfComingFromPath2 = min(val2.second, pathLenFrom2);
pair<long, long> ans;
if(minValIfComingFromPath1 == minValIfComingFromPath2) {
ans = pair<long, long>(max(pathLenFrom1, pathLenFrom2), minValIfComingFromPath1);
}else if(minValIfComingFromPath1 > minValIfComingFromPath2){
ans = pair<long, long>(pathLenFrom1, minValIfComingFromPath1);
}else {
ans = pair<long, long>(pathLenFrom2, minValIfComingFromPath2);
}
dp[x][y] = ans;
return ans;
}

int calculateMinimumHP(vector<vector<int>>& a) {
long inf = INT_MIN/3;
int m = a.size();
int n = a[0].size();
vector<vector<pair<long, long>>> dp(m+5, vector<pair<long, long>>(n+5, pair<long, long>(inf, inf)));
dp[0][0] = pair<long, long>(a[0][0], a[0][0]);
auto ans = func(m-1, n-1, a, dp);
int min_val = ans.second;
if(min_val > 0)
return 1;
return -1*min_val + 1;
}
};```