LC-2304 Medium LeetCode

2304. Minimum Path Cost in a Grid

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 67% Topics: Array, Dynamic Programming, Matrix

Reading material

Arrays & Hashing 12 min 1-D Dynamic Programming 16 min Math & Geometry 12 min

Reference solution (spoiler · python)

# Time:  O(m * n^2)
# Space: O(n)

# dp
class Solution(object):
    def minPathCost(self, grid, moveCost):
        """
        :type grid: List[List[int]]
        :type moveCost: List[List[int]]
        :rtype: int
        """
        dp = [[0]*len(grid[0]) for _ in xrange(2)]
        dp[0] = [grid[0][j] for j in xrange(len(grid[0]))]
        for i in xrange(len(grid)-1):
            for j in xrange(len(grid[0])):
                dp[(i+1)%2][j] = min(dp[i%2][k]+moveCost[x][j] for k, x in enumerate(grid[i]))+grid[i+1][j]
        return min(dp[(len(grid)-1)%2])

Solution from kamyu104/LeetCode-Solutions · MIT