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; } };