Leetcode 64: Minimum Path Sum

This is a variation of the the two previous problems (Unique Paths). So we just use dynamic programming to calculate running costs at each cell in the grid. We add the current grid cell cost to the lesser value of the running costs in the cells to the left and up. In the recursive solution be aware that we need to use return INT_MAX rather than 0 if the cell is out of bounds.

Source code for solutions:
Recursive with DP memoization
Iterative DP with O(n²) auxiliary space
Iterative DP with O(n) auxiliary space
Iterative DP with O(1) auxiliary space by modifying grid param

This entry was posted in programming and tagged , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published.