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


  • 3
    K

    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.


  • 0
    K

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

  • 0
    D

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


Log in to reply
 

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