# Can we start from dungeon[0][0] instead of dungeon[row-1][column-1]??

• Can we solve this by start from dungeon[0][0] instead of dungeon[row-1][column-1] and get final result at dungeon[row-1][column-1] using same or another dp approach??? Please help.

• The following is my solution which uses DP and starts from top left. Though it passes all the tests, I am not sure it is correct.

Elements in DP matrix are pairs: (maximum_health, the minimum to which health dropped)

The idea is: while iterating, keep 2 matrix: dp will maximize on the first pair element, dp2 will maximize on the second pair element.

class Solution {
public:
int calculateMinimumHP(std::vector<std::vector<int>> &dungeon) {
if (dungeon.empty() || dungeon[0].empty())
return 0;
auto dp = std::vector<std::vector<std::pair<int, int>>>(dungeon.size(), std::vector<std::pair<int, int>>(dungeon[0].size()));
auto dp2 = std::vector<std::vector<std::pair<int, int>>>(dungeon.size(), std::vector<std::pair<int, int>>(dungeon[0].size()));
dp[0][0] = {dungeon[0][0], dungeon[0][0]};
dp2[0][0] = {dungeon[0][0], dungeon[0][0]};
for (unsigned i = 1; i < dungeon[0].size(); i++)
{
dp[0][i] = {dp[0][i - 1].first + dungeon[0][i], std::min(dp[0][i - 1].second, dp[0][i - 1].first + dungeon[0][i])};
dp2[0][i] = {dp2[0][i - 1].first + dungeon[0][i], std::min(dp2[0][i - 1].second, dp2[0][i - 1].first + dungeon[0][i])};
}
for (unsigned j = 1; j < dungeon.size(); j++)
{
dp[j][0] = {dp[j - 1][0].first + dungeon[j][0], std::min(dp[j - 1][0].second, dp[j - 1][0].first + dungeon[j][0])};
dp2[j][0] = {dp2[j - 1][0].first + dungeon[j][0], std::min(dp2[j - 1][0].second, dp2[j - 1][0].first + dungeon[j][0])};
}
for (unsigned i = 1; i < dungeon.size(); i++)
for (unsigned j = 1; j < dungeon[i].size(); j++)
{
if (dp[i - 1][j].first > dp[i][j - 1].first)
dp[i][j] = {dp[i - 1][j].first + dungeon[i][j], std::min(dp[i - 1][j].first + dungeon[i][j], dp[i - 1][j].second)};
else
dp[i][j] = {dp[i][j - 1].first + dungeon[i][j], std::min(dp[i][j - 1].first + dungeon[i][j], dp[i][j - 1].second)};
std::pair<std::pair<int, int>, int> m = {dp[i][j - 1], std::min(dp[i][j - 1].second, dp[i][j - 1].first + dungeon[i][j])};
int k = std::min(dp2[i][j - 1].second, dp2[i][j - 1].first + dungeon[i][j]);
if (k > m.second || (k == m.second && dp2[i][j - 1].first > m.first.first))
m = {dp2[i][j - 1], k};
k = std::min(dp[i - 1][j].second, dp[i - 1][j].first + dungeon[i][j]);
if (k > m.second || (k == m.second && dp[i - 1][j].first > m.first.first))
m = {dp[i - 1][j], k};
k = std::min(dp2[i - 1][j].second, dp2[i - 1][j].first + dungeon[i][j]);
if (k > m.second || (k == m.second && dp2[i - 1][j].first > m.first.first))
m = {dp2[i - 1][j], k};
dp2[i][j] = {m.first.first + dungeon[i][j], m.second};
}
return std::max(1, -std::max(dp.back().back().second, dp2.back().back().second) + 1);
}
};

• If you use binary search, you can start from top left instead of bottom right.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.