forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathJeehay28.js
More file actions
86 lines (64 loc) Β· 1.65 KB
/
Jeehay28.js
File metadata and controls
86 lines (64 loc) Β· 1.65 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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
/**
* @param {number} m
* @param {number} n
* @return {number}
*/
// π DP
// Time Complexity: O(m*n)
// Space Complexity: O(n)
// Row 0: [1, 1, 1, 1]
// Row 1: [1, 2, 3, 4]
// Row 2: [1, 3, 6, 10]
// Initial dp: [1, 1, 1, 1]
// left = 1 (always starts with 1 for the first column)
// col = 1: left += dp[1] β left = 1 + 1 = 2 β dp[1] = left
// col = 2: left += dp[2] β left = 2 + 1 = 3 β dp[2] = left
// col = 3: left += dp[3] β left = 3 + 1 = 4 β dp[3] = left
// dp after row 1: [1, 2, 3, 4]
// Initial dp: [1, 2, 3, 4]
// left = 1
// col = 1: left += dp[1] β left = 1 + 2 = 3 β dp[1] = left
// col = 2: left += dp[2] β left = 3 + 3 = 6 β dp[2] = left
// col = 3: left += dp[3] β left = 6 + 4 = 10 β dp[3] = left
// dp after row 2: [1, 3, 6, 10]
var uniquePaths = function (m, n) {
let dp = new Array(n).fill(1);
for (let row = 1; row < m; row++) {
let left = 1;
for (let col = 1; col < n; col++) {
left += dp[col];
dp[col] = left;
}
}
return dp[n - 1];
};
/**
* @param {number} m
* @param {number} n
* @return {number}
*/
// π DFS
// Time Complexity: O(m*n)
// Space Complexity: O(m*n)
// var uniquePaths = function (m, n) {
// const memo = {};
// const dfs = (row, col) => {
// if (row === m - 1 && col === n - 1) {
// return 1;
// }
// let cnt = 0;
// const key = `${row}, ${col}`;
// if (key in memo) {
// return memo[key];
// }
// if (row + 1 < m) {
// cnt += dfs(row + 1, col);
// }
// if (col + 1 < n) {
// cnt += dfs(row, col + 1);
// }
// memo[key] = cnt;
// return cnt;
// };
// return dfs(0, 0);
// };