未分類

Unique Paths

Array, DynamicProgramming, Go, LeetCode

Unique Paths

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?

Note:

m and n will be at most 100.

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

Default:

1
2
3
func uniquePaths(m int, n int) int {
}

解答思路:

高中時再解這類路徑題目時都會先從簡單的部分開始以每格或點判斷走到該格有幾種可能，以題目給予的範例來說如下圖:

1
2
3
1  1  1  1  1  1  1
1  2  3  4  5  6  7
1  3  6 10 15 21 28

一開始走到最左側或最下側都只有一種可能，接著從起點鄰近的格子慢慢推會發現到該格的走法都是由到左側格子的走法再加上上側格子的走法，最後不斷推倒到最右下角的格子就是我們要的結果，再理解了如此的規律後便可以很容易的寫出要的程式碼。

程式碼解說:

因為需要不斷推倒每格走法的所有可能直到最右下角為止，所以一開始就需要初始化二元陣列來紀錄mxn走到每格的所有組合數

1
2
3
4
var paths [][]int
for k := 1; k <= m; k++ {
	paths = append(paths, make([]int, n))
}

接著就是初始化第一橫排與第一直列為1，因為一開始走到最左側或最下側都只有一種可能

1
2
3
4
5
6
for i := 0; i < m; i++ {
	paths[i][0] = 1
}
for j := 0; j < n; j++ {
	paths[0][j] = 1
}

最後則是根據先前所發現的規律，每格的走法都是由到左側格子的走法再加上上側格子的走法，將剩下的格子全數依序由左上到右下推倒完後，便直接回傳最右下角格子的走法數就是我們要的結果

1
2
3
4
5
6
for i := 1; i < m; i++ {
	for j := 1; j < n; j++ {
		paths[i][j] = paths[i-1][j] + paths[i][j-1]
	}
}
return paths[m-1][n-1]

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func uniquePaths(m int, n int) int {
	var paths [][]int
	for k := 1; k <= m; k++ {
		paths = append(paths, make([]int, n))
	}
	for i := 0; i < m; i++ {
		paths[i][0] = 1
	}
	for j := 0; j < n; j++ {
		paths[0][j] = 1
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			paths[i][j] = paths[i-1][j] + paths[i][j-1]
		}
	}
	return paths[m-1][n-1]
}

總結:

給一mxn所組成的方格，求出從最左上走到最右下共有幾走不同的走法，其做法就是先從簡單的部分開始以每格或點判斷走到該格有幾種可能，接著從起點鄰近的格子慢慢推會發現到該格的走法都是由到左側格子的走法再加上上側格子的走法，最後不斷推倒到最右下角的格子就是我們要的結果。

分享到