My accepted python solution with O(nm) time complexity and space complexity

  • 0

    Haven't seen much discussion in python solution, so I share mine here.
    This solution is based on the bottom-up solution of dynamic programming, I create another m*n matrix and use it to record the minimum hp required to rescue the princess from each room. The detailed code with comment is shown below:

    class Solution:
        # @param dungeon, a list of lists of integers
        # @return a integer
        def calculateMinimumHP(self, dungeon):
            m = len(dungeon)
            n = len(dungeon[0]) if m>0 else 0
            min_hp = 1  # we need at least 1 hp to make knight alive
            # record matrix: save the minimum hp required to enter each room and reach princess
            record = [[0 for i in range(n)] for i in range(m)]
            record[m-1][n-1] = min_hp if dungeon[m-1][n-1]>0 else abs(dungeon[m-1][n-1])+1  
            # when the bottom-right room contains a number less or equal than zero, the hp required 
            # to save the princess successfully is the absolute value of this number plus 1, 
            # otherwise it's min_hp which equals to 1 
            # set up the last row of the matrix backwardly
            need = record[m-1][n-1]
            for i in range(m-2,-1,-1):
                record[i][n-1] = need = max(min_hp, need-dungeon[i][n-1])
            # set up the last column of the matrix backwardly
            need = record[m-1][n-1]
            for i in range(n-2,-1,-1):
                record[m-1][i] = need = max(min_hp, need-dungeon[m-1][i])
            # fill the matrix from dungeon[m-2][n-2] to dungeon[0][0]    
            for i in range(m-2,-1,-1):
                for j in range(n-2,-1,-1):
                    need = record[i][j+1] if record[i][j+1]<record[i+1][j] else record[i+1][j]  
                    # move down or right - according to which direction has lower value
                    record[i][j] = max(min_hp, need-dungeon[i][j]) 
            return record[0][0]

    One thing to notice is by limiting the lower bound value at min_hp, we will only focus on the recent negative path and get rid of far away positive number naturally. For instance, both dungeon [[-10, -5, 35]] and [[-10, -5, 100]] will result in [[16,6,1]] since we don't mistakenly take into consideration the previous big positive number like 35 and 100.

    record[i][j] = max(min_hp, need-dungeon[i][j]) 

    Anyone also play this with python and want to share some ideas?

Log in to reply

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