forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathhi-rachel.py
More file actions
51 lines (38 loc) ยท 1.24 KB
/
hi-rachel.py
File metadata and controls
51 lines (38 loc) ยท 1.24 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
"""
https://leetcode.com/problems/unique-paths/description/
์๋๋ก ์ด๋ ํน์ (1, 0)
์ค๋ฅธ์ชฝ ์ด๋๋ง ๊ฐ๋ฅ (0, 1)
m => rows, n = cols
๋ก๋ด์ด (0, 0)์์ (m-1, n-1)์ ๋์ฐฉ ๊ฐ๋ฅํ unique paths ๊ฐ์๋ฅผ ๋ฐํ
ํ์ด ์๊ฐ: 16๋ถ
์ฒ์์ ์ด๋ป๊ฒ ํ์ด์ผ ํ ์ค ๋ชฐ๋์ง๋ง, ๊ทธ๋ฆผ์ ๊ทธ๋ ค๋ณด๋ฉฐ ๋์ ๊ท์น์ ์ฐพ์ (์, ์ผ์ชฝ ๊ฐ ๋ํด๋๊ฐ๊ธฐ)
paths[i][j] = paths[i-1][j] + paths[i][j-1]
TC: O(m * n)
SC: O(m * n)
"""
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
paths = [[0] * n for _ in range(m)]
paths[0][0] = 1
for i in range(m):
for j in range(n):
if i - 1 >= 0 and j - 1 >= 0:
paths[i][j] = paths[i - 1][j] + paths[i][j - 1]
else:
paths[i][j] = 1
return paths[m - 1][n - 1]
"""
๊ณต๊ฐ ๋ณต์ก๋ ์ต์ ํ ํ์ด - ๋ณต์ต ํ์
dp[i][j] = dp[i-1][j] + dp[i][j-1]
=> dp[j] = dp[j] + dp[j-1]
TC: O(m * n)
SC: O(n)
"""
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
# ์ฒซ ํ์ ๋ชจ๋ 1๋ก ์ด๊ธฐํ
dp = [1] * n
for i in range(1, m):
for j in range(1, n):
dp[j] = dp[j] + dp[j - 1]
return dp[-1]