BinarySearch 0013 Collecting Coins

Problem statement

https://binarysearch.com/problems/Collecting-Coins/

Solution

Equal to Leetcode 0064 Minimum Path Sum, but use min instead of max.

Complexity

It is O(mn) for time and space.

Code

class Solution:
    def solve(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 max(cands or [0]) + grid[i][j]
        
        return dfs(len(grid)-1, len(grid[0])-1)