forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsmosco.js
More file actions
45 lines (40 loc) Β· 1.18 KB
/
smosco.js
File metadata and controls
45 lines (40 loc) Β· 1.18 KB
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
* Unique Paths - μ‘°ν©λ‘ λ°©μ
*
* λ¬Έμ : m x n 그리λμμ (0,0)μμ (m-1, n-1)κΉμ§ κ°λ κ²½λ‘μ μ
* - μ€λ₯Έμͺ½ λλ μλλ‘λ§ μ΄λ κ°λ₯
*
* ν΅μ¬ μμ΄λμ΄:
* - μ΄ μ΄λ νμ: (m-1) + (n-1) = m+n-2λ²
* - μ€λ₯Έμͺ½ n-1λ², μλ m-1λ² μ΄λ νμ
* - μμλ§ λ€λ₯Έ μ‘°ν© λ¬Έμ : C(m+n-2, m-1) λλ C(m+n-2, n-1)
*
* μ: m=3, n=7
* - μ΄ 8λ² μ΄λ (μ€λ₯Έμͺ½ 6λ², μλ 2λ²)
* - C(8, 2) = 8!/(2!*6!) = 28
*
* μκ°λ³΅μ‘λ: O(min(m, n)) - μ‘°ν© κ³μ°
* 곡κ°λ³΅μ‘λ: O(1)
*
* @param {number} m
* @param {number} n
* @return {number}
*/
var uniquePaths = function(m, n) {
// C(m+n-2, m-1) = (m+n-2)! / ((m-1)! * (n-1)!)
// = (m+n-2) * (m+n-3) * ... * n / (m-1)!
let total = m + n - 2; // μ΄ μ΄λ νμ
let k = Math.min(m - 1, n - 1); // μμ μͺ½ μ ν (κ³μ° ν¨μ¨)
let result = 1;
// C(total, k) κ³μ°
for (let i = 1; i <= k; i++) {
result = result * (total - k + i) / i;
}
return result;
};
// ν
μ€νΈ
if (require.main === module) {
console.log(uniquePaths(3, 7)); // 28
console.log(uniquePaths(3, 2)); // 3
console.log(uniquePaths(1, 1)); // 1
}