Leecode 64. Minimum Path Sum

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

DP. Start from top and left edges. Formula is dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + board[i][j]. Note that top and left edges need to be added up.

Let's try even more enhanced one: no extra space.

Solution:

# T:O(m*n) S:O(1)
class Solution:
    # @param {integer[][]} grid
    # @return {integer}
    def minPathSum(self, grid):
        m, n = len(grid), len(grid[0])
        for i in xrange(1, n):
            grid[0][i] += grid[0][i-1]
        for j in xrange(1, m):
            grid[j][0] += grid[j-1][0]
        for i in xrange(1, m):
            for j in xrange(1, n):
                grid[i][j] += min(grid[i-1][j], grid[i][j-1])
        return grid[m-1][n-1]

Run Time: 72 ms