forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathHoonDongKang.ts
More file actions
69 lines (58 loc) · 1.92 KB
/
HoonDongKang.ts
File metadata and controls
69 lines (58 loc) · 1.92 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
60
61
62
63
64
65
66
67
68
69
/**
* [Problem]: [62] Unique Paths
* (https://leetcode.com/problems/unique-paths/description/)
*/
function uniquePaths(m: number, n: number): number {
//시간복잡도 O(2^(m*n))
//공간복잡도 O(m*n)
// Time Limit Exceeded
function dfsFunc(m: number, n: number): number {
let result: number = 0;
function dfs(row: number, col: number) {
if (row === m - 1 && col === n - 1) result++;
if (row + 1 < m) dfs(row + 1, col);
if (col + 1 < n) dfs(row, col + 1);
}
dfs(0, 0);
return result;
}
//시간복잡도 O(m*n)
//공간복잡도 O(m*n)
function memoizationFunc(m: number, n: number): number {
let memo = new Map<string, number>();
function dfs(row: number, col: number) {
const key = `${row}|${col}`;
if (memo.has(key)) return memo.get(key);
if (row === m - 1 && col === n - 1) return 1;
if (row >= m || col >= n) return 0;
const result = dfs(row + 1, col) + dfs(row, col + 1);
memo.set(key, result);
return result;
}
return dfs(0, 0);
}
//시간복잡도 O(m*n)
//공간복잡도 O(m*n)
function dpFunc(m: number, n: number): number {
let dp: number[][] = Array.from({ length: m }, () => Array(n).fill(1));
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
//시간복잡도 O(m*n)
//공간복잡도 O(n)
function optimizationFunc(m: number, n: number): number {
let dp: number[] = new Array(n).fill(1);
for (let i = 1; i < m; i++) {
let left = 1;
for (let j = 1; j < n; j++) {
dp[j] += left;
left = dp[j];
}
}
return dp[n - 1];
}
}