forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsoobing.ts
More file actions
59 lines (49 loc) ยท 1.66 KB
/
soobing.ts
File metadata and controls
59 lines (49 loc) ยท 1.66 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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
* ๋ฌธ์ ์ค๋ช
* - mํ๊ณผ n์ด์ ๊ทธ๋ํ์์ ์ค๋ฅธ์ชฝ ์๋์ ๋๋ฌํ ์ ์๋ ๋ฐฉ๋ฒ์ ๊ฐ์ง์
* - ์๋, ์ค๋ฅธ์ชฝ์ผ๋ก๋ง ์ด๋ ๊ฐ๋ฅ
*
* ์์ด๋์ด
* 1) DP
* - ์ฒซ๋ฒ์งธ ํ, ์ฒซ๋ฒ์งธ ์ด์ ์ ์ธํ๊ณ ๋์๋ (m - 1)๋ฒ ์๋ + (n - 1)๋ฒ ์ค๋ฅธ์ชฝ์ ๋ํ ๊ฐ์ด ํ์ฌ ์์น์ ์ฌ ์ ์๋ ๋ฐฉ๋ฒ์.
* - ์ ๋ถ ๊ฑฐ์น๋ค์ ๊ฐ์ฅ ์ค๋ฅธ์ชฝ ์๋์ ๊ฐ์ ๋ฐํํ๋ฉด ์ ๋ต
* 2) ์กฐํฉ -> factorial์ ๊ฒฝ์ฐ Maximum call stack size exceed ๋ฐ์
* - ์๋๋ก ์ด๋ ๊ฐ๋ฅํ ์(m-1), ์ค๋ฅธ์ชฝ์ผ๋ก ์ด๋ ๊ฐ๋ฅํ ์ (n-1)์ ์กฐํฉ
* - (m + n - 2)! / (m - 1)! * (n - 1)!
*/
function uniquePaths(m: number, n: number): number {
const dp = Array(m).fill(Array(n).fill(1));
for (let r = 1; r < m; r++) {
for (let c = 1; c < n; c++) {
dp[r][c] = dp[r - 1][c] + dp[r][c - 1];
}
}
return dp[m - 1][n - 1];
}
/**
* factorial ํ์ด -> ์๋ฌ๋ฐ์
*
function uniquePaths(m: number, n: number): number {
function factorial(n: number) {
if (n === 1) return 1;
return n * factorial(n - 1);
}
return factorial(m + n - 2)! / (factorial(m - 1) * factorial(n - 1));
}
*/
/**
* ์ฝ๋ ๋ฆฌ๋ทฐ ๋ต์ ๊ธฐ๋ก
function uniquePaths(m: number, n: number): number {
const memo = new Map<string, number>();
const traverse = (row: number, col: number) => {
if (row >= m || col >= n) return 0;
if (row === m - 1 && col === n - 1) return 1;
const key = `${row}-${col}`;
if (memo.has(key)) return memo.get(key);
const result = traverse(row + 1, col) + traverse(row, col + 1);
memo.set(key, result);
return result;
};
return traverse(0, 0);
}
*/