Leetcode 0064 Minimum Path Sum

Problem statement

https://leetcode.com/problems/minimum-path-sum/

Solution

Classical DP problem with complexity O(nm), see problems 0062, 0063.

Complexity

Time and space complexity is O(mn)

Code

class Solution:
    def minPathSum(self, grid):
        @lru_cache(None)
        def dfs(i, j):
            cands = []
            if j > 0: cands.append(dfs(i, j-1))
            if i > 0: cands.append(dfs(i-1, j))
            return min(cands or [0]) + grid[i][j]
        
        return dfs(len(grid)-1, len(grid[0])-1)