Concise C# solution with explanation

  • 0

    This is based on flyingPig's post which I felt was the best even it doesn't have the highest votes. What I have done is port it to C# and make it a little more concise. The solution has an O(N) time complexity, where N is the total (m * n) number of elements in the input array with a O(n/N) space complexity

    Important points to consider:

    • Where are looking for the minimum HP prior to entering room (0,0).

    • The Knight can only move down or right

    • The Knight's HP can never reach zero and has unlimited (< 2^32 - 1) HP potential

    • The DP solution represents the Knight's minimum HP.

    • The DP is filled with int.MaxValue so that when a room is unvisited, it's value is like being "unassigned", which int.MaxValue makes a good candidate for.

    • The initial DP assumes the Knight's HP is 1 until a condition is found that changes that.

    • The iteration of the dungeon happens from the bottom and right to ensure the Knight's path from top and left is one that is using the minimum HP, which aligns with the requirement of the Knight's initial HP @ (0,0) versus the maximum HP @ (M-1, N-1)

    • The iteration order is the major factor in controlling the Knight's path through the dungeon, but the calculation done is such a way that the best path is chosen. For each row in the dungeon, the minimum is always taken between DPj and DPj+1 so DPj is always coming from the right on dungeon[i,j].

        public int CalculateMinimumHP(int[,] dungeon)
            int m = dungeon.GetUpperBound(0) + 1;
            int n = dungeon.GetUpperBound(1) + 1;
            int[] initialHP = new int[n + 1];
            Array.Fill(initialHP, int.MaxValue);
            initialHP[n - 1] = 1;
            for (int i = m - 1; i >= 0; i--)
                for (int j = n - 1; j >= 0; j--)
                    initialHP[j] = Math.Max(1 , Math.Min(initialHP[j], initialHP[j + 1]) - dungeon[i, j]);
            return initialHP[0];

Log in to reply

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