2022 - 2023 Class 13

Class Slides

Solution to problem on slide 4:

This is a dynamic programming (dp) problem where you can store the minimum cost to get to each point and use those minimum costs to find the next minimum cost etc. Here is my solution which runs in O(NM) time where N and M are sides of the grid.

class Solution(object):
    def minPathSum(self, grid):
        n = len(grid)
        m = len(grid[0])
        min_dist = [[101*200 for i in range(m)] for i in range(n)]
        min_dist[0][0] = grid[0][0]
        for i in range(0,n):
            for j in range(0,m):
                if i>0:
                    min_dist[i][j] = min(min_dist[i][j],min_dist[i-1][j]+grid[i][j])
                if j>0:
                    min_dist[i][j] = min(min_dist[i][j],min_dist[i][j-1]+grid[i][j])
        return min_dist[n-1][m-1]

There is no homework for the next 2 weeks. Enjoy!