Leetcode - minimum-path-sum

Input:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

This is a dp question. Create a d matrix to store every point of the current sum. To calculate the latest sum, use the minium of the previous point sum and then add current grid number.

d[i][j] = min(d[i][j-1], d[i-1][j]) + grid[i][j]

Handle the edge case when it comes to i = 0 and j = 0

func minPathSum(grid [][]int) int {
	if len(grid) == 0 || len(grid[0]) == 0 {
		return 0
	}
	d := make([][]int, len(grid))
	for i := 0; i < len(grid); i++ {
		d[i] = make([]int, len(grid[0]))
	}

	r := len(grid)
	c := len(grid[0])

	d[0][0] = grid[0][0]

	for i := 0; i < r; i++ {
		for j := 0; j < c; j++ {
			if i > 0 && j > 0 {
				d[i][j] = min(d[i-1][j], d[i][j-1]) + grid[i][j]
			}
			if i == 0 && j != 0 {
				d[i][j] = d[i][j-1] + grid[i][j]
			}
			if j == 0 && i != 0 {
				d[i][j] = d[i-1][j] + grid[i][j]
			}
		}
	}

	return d[r-1][c-1]
}

func min(a, b int) int {
	if a < b {
		return a
	}

	return b
}

# @param {Integer[][]} grid
# @return {Integer}
def min_path_sum(grid)
    return 0 if grid.length == 0 || grid[0].length == 0
    r = grid.length
    c = grid[0].length
    
    dp = Array.new(r){Array.new(c, 0)}
    dp[0][0] = grid[0][0]
    for i in 0..r-1 do
        for j in 0..c-1 do
            if i > 0 && j > 0
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
            end
            dp[i][j] = dp[i][j-1] + grid[i][j] if i == 0 && j != 0
            dp[i][j] = dp[i-1][j] + grid[i][j] if j == 0 && i != 0
        end
    end
     
    return dp[r-1][c-1]
end

def min(a, b)
    a < b ? a : b
end

• 相关文章
• 全局相关文章