未分類

Triangle

Array, DynamicProgramming, Go, LeetCode

Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example:

Given the following triangle

1
2
3
4
5
6
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

Note:

Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

提示 解題應用
Array 要使空間複雜度降至最低需碰壞原始資料
DynamicProgramming 規律觀查

Default:

1
2
3
func minimumTotal(triangle [][]int) int {
}

解答思路:

這題與二元樹中要找最短路徑的意思一樣，只是這次是三角形或金字塔而且是陣列組合，相對二元樹來說能直接讀取每個位置的值就讓題目簡單很多，而題目只要求空間複雜度不要超過O(n)，但我們可以用的更少，一般來說通常是空間換取時間或時間換取空間，而如果在時間固定的情況下想要讓空間花費更少大多就只有碰壞儲存的原始資料，以這題來說就是只利用題目所給予的二元陣列來儲存結果，從最上層開始將路徑值向下做累加，如果有兩個路徑可能會累加至同一地方，就選擇最小的進行累加，最後在三角形底部的每個值就會是到該點的最短路徑，而題目只要求能到底部的最短路徑就好，因此只要再從中找出最小值即可。

程式碼解說:

一開始先將最小值初始化為int的32位元極大值以方便後續進行比較，接著就從用巢狀迴圈取出三角形中的所有值進行累加，如果發現已經累加到三角形的底部，這時就開始比較哪一條到底部的路徑最短(值最小)，而如果尚未累加到底部就繼續做累加，這邊三角形任一層中的值分作四塊來比較，最左側的值、與左邊值的比較、與右邊值的比較、最右側的值，透過觀查可以發現到三角形的最左右兩側值都只能由前一層最左右兩側值來累加(路徑只有最外側會經過)，所以只要是最外側的值就直接向下往兩旁進行累加，至於同一層之中任意一個值左邊如果存在其它值，那麼向下累加時勢必會出現兩個路徑累加至同一地方，因此就要與左邊比較誰目前的路徑較短來做挑選，反之如果右邊存在其它值則做法一樣，最後要注意到的是如果同一層之中有值相同且相鄰的情況(或目前累加的路徑長度相同)，那麼在與左右兩邊存在值比較時的兩種情況，只要固定一邊向下做累加就好，就可以避免重覆累加的情況發生(ex: AB兩值相鄰且相同，兩個路徑向下都會累加至同一地方C，A的右側存在B，B的左側存在A，因此針對相同的情況只要固定一邊來向下累加就可以避免重覆累加)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
min := math.MaxInt32
for ir, row := range triangle {
	for is, step := range row {
		if ir+1 == len(triangle) {
			if step < min {
				min = step
			}
			continue
		}
		if is == 0 {
			triangle[ir+1][0] += step
		}
		if is-1 >= 0 && step < row[is-1] {
			triangle[ir+1][is] += step
		}
		if is+1 < len(row) && step <= row[is+1] {
			triangle[ir+1][is+1] += step
		}
		if is+1 == len(row) {
			triangle[ir+1][is+1] += step
		}
	}
}
return min

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func minimumTotal(triangle [][]int) int {
	min := math.MaxInt32
	for ir, row := range triangle {
		for is, step := range row {
			if ir+1 == len(triangle) {
				if step < min {
					min = step
				}
				continue
			}
			if is == 0 {
				triangle[ir+1][0] += step
			}
			if is-1 >= 0 && step < row[is-1] {
				triangle[ir+1][is] += step
			}
			if is+1 < len(row) && step <= row[is+1] {
				triangle[ir+1][is+1] += step
			}
			if is+1 == len(row) {
				triangle[ir+1][is+1] += step
			}
		}
	}
	return min
}

總結:

要從三角形/金字塔的陣列組合中找出從頂到到底部的最短路徑，如果又有要求空間複雜度不要超過O(n)，碰壞儲存的原始資料便能使空間複雜度降至最低，利用題目所給予的二元陣列來儲存結果，從最上層開始將路徑值向下做累加，如果有兩個路徑可能會累加至同一地方，就選擇最小的進行累加，最後在三角形底部的每個值就會是到該點的最短路徑，如果只要求能到底部的最短路徑，就只要再從中找出最小值即可。

分享到