There is a robot on an m x n grid.
The robot is initially located at the top-left corner (i.e., grid[0][0]).
The robot tries to move to the bottom-right corner (i.e., grid[m – 1][n – 1]).
The robot can only move either down or right at any point in time.
Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.
The test cases are generated so that the answer will be less than or equal to 2 * 109.
這裡有一個機器人在 m x n 的方格。 機器人最初的位置在左上方的角落(ex. grid[0][0]) 機器人嘗試移動到右下方的角落(ex. grid[m - 1][n - 1]。 機器人一次只可以移動「下」或「右」到任何點。 給予兩個整數 m 和 n，讓機器人可以開始搜尋到右下角，回傳可能到達路徑的次數。 測試的案例中，答案小於等於 2 * 109。
Example 1:
Input: m = 3, n = 7 Output: 28
Example 2:
Input: m = 3, n = 2 Output: 3 Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner: 1. Right -> Down -> Down 2. Down -> Down -> Right 3. Down -> Right -> Down
Solution:
1. 宣告存放數值的陣列。(ex. [[0, 0, 0],[0, 0, 0]]
2. 放入 i 跟 j 代表起點格子，直到終點 m 跟 n。
+------+ +------+ | 1, 1 | => | m, n | +------+ +------+
3. 預設起點步數符合為 1。
4. 不符，則從終點依序 temp[i – 1][j] 與 temp[i][j – 1] 回到起點。
5. 將過程中的符合 m 與 n 的範圍進行加總。
Code.1: Method of exhaustion 窮舉
var uniquePaths = function(m, n) {
const searchPath = (m, n, row, column) => {
if (row === m && column === n) return 1
if (row > m || column > n) return 0
return searchPath(m, n, row, column + 1) + searchPath(m, n, row + 1, column)
}
return searchPath(m, n, 1, 1)
};
section.1
m = 3, n = 2 => m x 2 = 3 x 2 grid
一Start一
+------+------+
| 1, 1 | 1, 2 |
+------+------+
| 2, 1 | 2, 2 |
+------+------+
| 3, 1 | 3, 2 |
+------+------+
一End一
section.2
m = 3, n = 2, r = row, c = column
(r, c)
|-------------(1, 1)-----------------|
|---(1, 2)---| |------(2, 1)------|
(1, 3) |---(2, 2)---| |---(2, 2)---| |---(3, 1)---|
0 (2, 3) (3, 2) (2, 3) (3, 2) (3, 2) (4, 1)
0 1 0 1 1 0
每一次的路徑選擇分為「右邊 + 1」或「左邊 + 1」，
當 row > m(3) 時為 0，而 column > n(2) 時為 0，
且剛好 row === m，與 column === n」的時候，回傳 1，
最後加總所有的 1。
Code.2: Method of Recursion and Hashmap 遞迴和散列圖
var uniquePaths = function(m, n) {
let temp = {}
const searchPath = function(m, n, temp) {
if (m === 1|| n === 1) return 1
temp[`${m}-${n}`] = searchPath(m - 1, n, temp) + searchPath(m, n - 1, temp)
console.log(temp)
return temp[`${m}-${n}`]
}
return searchPath(m, n, temp)
};
section.1
m = 3, n = 2 => m x 2 = 3 x 2 grid
一End一
+------+------+
| 1, 1 | 1, 2 |
+------+------+
| 2, 1 | 2, 2 |
+------+------+
| 3, 1 | 3, 2 |
+------+------+
一Start一
section.2
m = 3, n = 2, r = row, c = column
(m, 2)
|-------------(3, 2)-------------------|
|------(2, 2)------| |------(3, 1)---|
|---(1, 2)---| |---(2, 1)---| |---(2, 1)---| (3, 0)
(0, 2) (1, 1) (1, 1) (2, 0) (1, 1) (2, 0) 0
0 1 1 0 1 0
Code.3: Method of Dynamic Programming 動態規劃
var uniquePaths = function(m, n) {
let temp = new Array(m + 1).fill(1).map(x => new Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (i === 1 && j === 1) {
temp[i][j] = 1
} else {
temp[i][j] = temp[i - 1][j] + temp[i][j - 1]
}
}
}
return temp[m][n]
}
FlowChart:
Example 1: Method of Dynamic Programming 動態規劃
Input: m = 3, n = 7 -m: 0~3
------------------------+
temp = [[ 0, 0, 0, 0, | 0
0, 0, 0, 0 ], |
[ 0, 0, 0, 0, | 1
0, 0, 0, 0 ], |
[ 0, 0, 0, 0, | 2
0, 0, 0, 0 ], |
[ 0, 0, 0, 0, | 3
0, 0, 0, 0 ]] |
------------------------+
-n: 0~7 ( 0, 1, 2, 3,
4, 5, 6, 7 )
step.1
i = 1, j = 1
Array[1][1] = 1
:
temp = [[ 0, 1, 0, 0, -m: 1
0, 0, 0, 0 ],
:
i = 1, j = 2
Array[1][2] = Array[0][2] + Array[1][1] => 0 + 1 = 1
:
temp = [[ 0, 1, 1, 0, -m: 1
0, 0, 0, 0 ],
:
i = 1, j = 3
Array[1][3] = Array[0][3] + Array[1][2] => 0 + 1 = 1
:
temp = [[ 0, 1, 1, 1, -m: 1
0, 0, 0, 0 ],
:
i = 1, j = 4
Array[1][4] = Array[0][4] + Array[1][3] => 0 + 1 = 1
:
temp = [[ 0, 1, 1, 1, -m: 1
1, 0, 0, 0 ],
:
i = 1, j = 5
Array[1][5] = Array[0][5] + Array[1][4] => 0 + 1 = 1
:
temp = [[ 0, 1, 1, 1, -m: 1
1, 1, 0, 0 ],
:
i = 1, j = 6
Array[1][6] = Array[0][6] + Array[1][5] => 0 + 1 = 1
:
temp = [[ 0, 1, 1, 1, -m: 1
1, 1, 1, 0 ],
:
i = 1, j = 7
Array[1][7] = Array[0][7] + Array[1][6] => 0 + 1 = 1
:
temp = [[ 0, 1, 1, 1, -m: 1
1, 1, 1, 1 ],
:
round.1
------------------------+
temp = [[ 0, 0, 0, 0, |
0, 0, 0, 0 ], |
[ 0, 1, 1, 1, |
1, 1, 1, 1 ], |
[ 0, 0, 0, 0, |
0, 0, 0, 0 ], |
[ 0, 0, 0, 0, |
0, 0, 0, 0 ]] |
------------------------+
step.2
i = 2, j = 1
Array[2][1] = Array[1][1] + Array[2][0] => 1 + 0 = 1
:
temp = [[ 0, 1, 0, 0, -m: 2
0, 0, 0, 0 ],
:
i = 2, j = 2
Array[2][2] = Array[1][2] + Array[2][1] => 1 + 1 = 2
:
temp = [[ 0, 1, 2, 0, -m: 2
0, 0, 0, 0 ],
:
i = 2, j = 3
Array[2][3] = Array[1][3] + Array[2][2] => 1 + 2 = 3
:
temp = [[ 0, 1, 2, 3, -m: 2
0, 0, 0, 0 ],
:
i = 2, j = 4
Array[2][4] = Array[1][4] + Array[2][3] => 1 + 3 = 4
:
temp = [[ 0, 1, 2, 3, -m: 2
4, 0, 0, 0 ],
:
i = 2, j = 5
Array[2][5] = Array[1][5] + Array[2][4] => 1 + 4 = 5
:
temp = [[ 0, 1, 2, 3, -m: 2
4, 5, 0, 0 ],
:
i = 2, j = 6
Array[2][6] = Array[1][6] + Array[2][5] => 1 + 5 = 6
:
temp = [[ 0, 1, 2, 3, -m: 2
4, 5, 6, 0 ],
:
i = 2, j = 7
Array[2][7] = Array[1][7] + Array[2][6] => 1 + 6 = 7
:
temp = [[ 0, 1, 2, 3, -m: 2
4, 5, 6, 7 ],
:
round.2
------------------------+
temp = [[ 0, 0, 0, 0, |
0, 0, 0, 0 ], |
[ 0, 1, 1, 1, |
1, 1, 1, 1 ], |
[ 0, 1, 2, 3, |
4, 5, 6, 7 ], |
[ 0, 0, 0, 0, |
0, 0, 0, 0 ]] |
------------------------+
step.3
i = 3, j = 1
Array[3][1] = Array[2][1] + Array[3][0] => 1 + 0 = 1
:
temp = [[ 0, 1, 0, 0, -m: 3
0, 0, 0, 0 ],
:
i = 3, j = 2
Array[3][2] = Array[2][2] + Array[3][1] => 2 + 1 = 3
:
temp = [[ 0, 1, 3, 0, -m: 3
0, 0, 0, 0 ],
:
i = 3, j = 3
Array[3][3] = Array[2][3] + Array[3][2] => 3 + 3 = 6
:
temp = [[ 0, 1, 3, 6, -m: 3
0, 0, 0, 0 ],
:
i = 3, j = 4
Array[3][4] = Array[2][4] + Array[3][3] => 4 + 6 = 10
:
temp = [[ 0, 1, 3, 6, -m: 3
10, 0, 0, 0 ],
:
i = 3, j = 5
Array[3][5] = Array[2][5] + Array[3][4] => 5 + 10 = 15
:
temp = [[ 0, 1, 3, 5, -m: 3
10, 15, 0, 0 ],
:
i = 3, j = 6
Array[3][6] = Array[2][6] + Array[3][5] => 6 + 15 = 21
:
temp = [[ 0, 1, 3, 5, -m: 3
10, 15, 21, 0 ],
:
i = 3, j = 7
Array[3][7] = Array[2][7] + Array[3][6] => 7 + 21 = 28
:
temp = [[ 0, 1, 3, 5, -m: 3
10, 15, 21, 28 ],
:
round.3
----------------------------+
temp = [[ 0, 0, 0, 0, |
0, 0, 0, 0 ], |
[ 0, 1, 1, 1, |
1, 1, 1, 1 ], |
[ 0, 1, 2, 3, |
4, 5, 6, 7 ], |
[ 0, 1, 3, 5, |
10, 15, 21, 28 ]] |
----------------------------+
Example 2: Method of Dynamic Programming 動態規劃
Input: m = 3, n = 2 --------------------------------------------+ temp = [[0,0,0], [0,0,0], [0,0,0], [0,0,0]] | --------------------------------------------+ -m: 0 1 2 3 -n: 0 1 2 step.1 i = 1, j = 1 Array[1][1] = 1 temp = [[0,0,0], [0,0,0], [0,0,0], [0,0,0]] i = 1, j = 2 temp[0][2] + temp[1][1] => 0 + 1 = 1 Array[1][2] = 1 temp = [[0,0,0], [0,1,0], [0,0,0], [0,0,0]] step.2 i = 2, j = 1 temp[1][1] + temp[2][0] => 1 + 0 = 1 Array[2][1] = 1 temp = [[0,0,0], [0,1,1], [0,0,0], [0,0,0]] i = 2, j = 2 temp[1][2] + temp[2][1] => 1 + 1 = 2 Array[2][2] = 2 temp = [[0,0,0], [0,1,1], [0,1,0], [0,0,0]] step.3 i = 3, j = 1 temp[2][1] + temp[3][0] => 1 + 0 = 1 Array[3][1] = 1 temp = [[0,0,0], [0,1,1], [0,1,2], [0,0,0]] i = 3, j = 2 temp[2, 2] + temp[3, 1] => 2 + 1 = 3 Array[3][2] = 3 temp = [[0,0,0], [0,1,1], [0,1,2], [0,1,0]] return temp[3][2] = 3
.fill()
.fill()：將陣列中第一到最後的每個位置填入一個靜態的數值。 const array1 = [1, 2, 3, 4]; // fill with 0 from position 2 until position 4 console.log(array1.fill(0, 2, 4)); // expected output: [1, 2, 0, 0] // fill with 5 from position 1 console.log(array1.fill(5, 1)); // expected output: [1, 5, 5, 5] console.log(array1.fill(6)); // expected output: [6, 6, 6, 6]
.map()
.map()：建立一個新的陣列，將原陣列中的每個元素透過函式運算後回傳結果。 const array1 = [1, 4, 9, 16]; // pass a function to map const map1 = array1.map(x => x * 2); console.log(map1); // expected output: Array [2, 8, 18, 32]
參考資料：LeetCode 雙刀流：62. Unique Paths