未分類

Minimum Path Sum

Array, DynamicProgramming, Go, LeetCode

Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note:

You can only move either down or right at any point in time.

提示 解題應用
Array Array/Slice
DynamicProgramming 規律觀查

Default:

1
2
3
func minPathSum(grid [][]int) int {
}

解答思路:

建議可以先參考先前Unique Paths的解法，大致上概念類似，只是這次所有的格子都有了加權數，也就是說明明同樣是一格但實際長度卻不一樣的意思，要找出最短路徑的話從原本到該格的走法做總合改為選擇到該格最短路徑的距離才做累加，一開始走到最左側或最下側因為只有一種可能，所以加權數的路徑便分別一路累加到底(走法只有一種但路徑是要算長度所以要總合先前走過的長度)，接著從起點鄰近的格子慢慢推會發現到該格最短的距離都是比較左側格子已累加的距離與上側格子已累加的距離，如果哪側比較短就只將那一側的距離與該格的加權數做累加，最後不斷推倒到最右下角的格子就是我們要的結果，再理解了如此的規律後便可以很容易的寫出要的程式碼。

程式碼解說:

因為這次二元陣列要儲存的是加權數(路徑長度)到該格的累加，所以就不再初始化一個新的二元陣列來分開儲存，直接拿原本每格儲存的加權值來做累加，一開始先取出二元陣列的大小有幾橫排m與幾直列n以方便我們做遍歷，接著因為從開始走到最左側或最下側因為只有一種可能，所以加權數的路徑便分別一路累加到底

1
2
3
4
5
6
7
8
m := len(grid)
n := len(grid[0])
for i := 1; i < m; i++ {
	grid[i][0] += grid[i-1][0]
}
for j := 1; j < n; j++ {
	grid[0][j] += grid[0][j-1]
}

最後則是根據先前所發現的規律，到該格最短的距離都是比較左側格子已累加的距離與上側格子已累加的距離，如果哪側比較短就只將那一側的距離與該格的加權數做累加，待最右下角格子的最短距離算出來後就是我們要的結果

1
2
3
4
5
6
7
8
9
10
for i := 1; i < m; i++ {
	for j := 1; j < n; j++ {
		if grid[i-1][j] < grid[i][j-1] {
			grid[i][j] += grid[i-1][j]
		} else {
			grid[i][j] += grid[i][j-1]
		}
	}
}
return grid[m-1][n-1]

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func minPathSum(grid [][]int) int {
	m := len(grid)
	n := len(grid[0])
	for i := 1; i < m; i++ {
		grid[i][0] += grid[i-1][0]
	}
	for j := 1; j < n; j++ {
		grid[0][j] += grid[0][j-1]
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			if grid[i-1][j] < grid[i][j-1] {
				grid[i][j] += grid[i-1][j]
			} else {
				grid[i][j] += grid[i][j-1]
			}
		}
	}
	return grid[m-1][n-1]
}

總結:

建議可以先參考先前Unique Paths的解法，大致上概念類似，只是這次所有的格子都有了加權數，要找出最短路徑的話從原本到該格的走法做總合改為選擇到該格最短路徑的距離才做累加，一開始走到最左側或最下側因為只有一種可能，所以加權數的路徑便分別一路累加到底，接著從起點鄰近的格子慢慢推會發現到該格最短的距離都是比較到左側格子已累加的距離與上側格子已累加的距離，比較短的那側才與該格的加權數做累加，最後不斷推倒到最右下角的格子就是我們要的結果。

分享到