Dynamic programming in Python


  • 0
    H
    class Solution(object):
        def minPathSum(self, grid):
            """
            :type grid: List[List[int]]
            :rtype: int
            """
            m = len(grid)
            if m == 0: return 0
            n = len(grid[0])
            if n == 0: return 0
            # initialize DP table
            table = [[0 for j in range(n)] for i in range(m)]
            table[0][0] = grid[0][0]
            for j in range(1, n):   table[0][j] = table[0][j-1] + grid[0][j]
            for i in range(1, m):   table[i][0] = table[i-1][0] + grid[i][0]
            # DP
            for i in range(1, m):
                for j in range(1, n):
                    table[i][j] = min(table[i-1][j], table[i][j-1]) + grid[i][j]
            return table[m-1][n-1]
    

Log in to reply
 

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