forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathJeehay28.ts
More file actions
41 lines (32 loc) · 883 Bytes
/
Jeehay28.ts
File metadata and controls
41 lines (32 loc) · 883 Bytes
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
// Memoized DFS
// TC: O(m * n)
// SC: O(m * n)
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);
}
// DP
// TC: O(m * n)
// SC: O(m * n)
/*
function uniquePaths(m: number, n: number): number {
// 1, 1, 1
// 1, 1+1=2, 1+(1+1)=3
const dp = 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];
};
*/