64 Minimum Path Sum

We need to enumerate all paths and then keep track of the smallest path sum.

Again, let’s use reduction to reduce this problem into smaller problems. To comupte the minimum path sum from (0,0) to (m,n), we would first need to know the minimum path sum till (m-1, n) and (m, n-1).

Once we have reduced our problem, we can put into a recursive statement and we are done.

Code

Python3

  def minPathSum(self, grid: List[List[int]]) -> int:
      
 
      @functools.cache
      def compute_sum(i, j):
          if i < 0 or j < 0:
              return sys.maxsize
          
          # if i == 0 and j == 0:
          #     return grid[i][j]
          
          return grid[i][j] + min(compute_sum(i-1, j), compute_sum(i, j-1))
      
 
      m, n = len(grid), len(grid[0])
 
      return compute_sum(m-1, n-1)

Big O Analysis

• Runtime

  The runtime complexity here is $O(N)$ since are caching - which reduces the $O(2^N)$ to linear time.

• Memory

  The memory usage is $O(N)$ since we are caching.

— A

GitHub | Twitter