forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathKwonNayeon.py
More file actions
72 lines (56 loc) Β· 2 KB
/
KwonNayeon.py
File metadata and controls
72 lines (56 loc) Β· 2 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
"""
Constraints:
- 1 <= m, n <= 100
<Solution 1: μ‘°ν© νμ©>
Time Complexity: O(1)
- math.comb() μ¬μ©
Space Complexity: O(1)
- μΆκ° κ³΅κ° νμμμ
νμ΄ λ°©λ²:
- μ€λ₯Έμͺ½ μλ μ½λλ‘ κ°λ μ λν¬ν λ°©λ²μ κ°―μ μ°ΎκΈ°
1. (m-1)λ² μλλ‘, (n-1)λ² μ€λ₯Έμͺ½μΌλ‘ κ°μΌν¨ -> μ΄ (m+n-2)λ² μ΄λ
2. κ²°κ΅ (m+n-2)λ²μ μ΄λ μ€ (n-1)λ²μ μ€λ₯Έμͺ½ μ΄λμ μ ννλ μ‘°ν©μ μ
3. Combination 곡μ μ μ©: (m+n-2)C(n-1)
- C(m+n-2, n-1) = (m+n-2)! / ((n-1)! Γ (m-1)!)
- νμ΄κ° κ°κ²°ν¨, νμ§λ§ ν° μμμ μ€λ²νλ‘μ° κ°λ₯μ± μμ
"""
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
from math import comb
return comb(m+n-2, n-1)
"""
<Solution 2: DP νμ©>
Time Complexity: O(m * n)
- mμ row, nμ columnμ κΈΈμ΄
- λ©λͺ¨μ΄μ μ΄μ
νμ©, λͺ¨λ μ’νμμ μ¬κ· ν¨μμ νΈμΆμ΄ λ± νλ²λ§ μΌμ΄λκΈ° λλ¬Έ
Space Complexity: O(m * n)
- ν¨μμ νΈμΆ κ²°κ³Όλ₯Ό μ μ₯νλλ° κ²©μμ λμ΄μ λΉλ‘νλ 곡κ°μ΄ νμ
νμ΄λ°©λ²:
- ꡬνμ΄ λ³΅μ‘ν¨, νμ§λ§ ν° μμμλ μμ μ μ
- μ¬κ·μ λ©λͺ¨μ΄μ μ΄μ
μ νμ©ν Top-down DP μ κ·Όλ²
- νμ¬ μμΉμμ λͺ©μ μ§κΉμ§μ κ²½λ‘ μ = μλλ‘ μ΄λ + μ€λ₯Έμͺ½μΌλ‘ μ΄λ
2x3 그리λ μμ:
κ° μμΉμμ λͺ©μ μ§κΉμ§ κ°λ κ²½λ‘ μ:
(0,0)=3 (0,1)=2 (0,2)=1
(1,0)=1 (1,1)=1 (1,2)=1
μμΉ (0,0)μμ μμ:
dfs(0,0) = dfs(1,0) + dfs(0,1) = 1 + 2 = 3
κ²½λ‘ 3κ°:
1. μ€λ₯Έμͺ½, μ€λ₯Έμͺ½, μλ
2. μ€λ₯Έμͺ½, μλ, μ€λ₯Έμͺ½
3. μλ, μ€λ₯Έμͺ½, μ€λ₯Έμͺ½
"""
from functools import cache
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
@cache
def dfs(row, col):
if row == m - 1 and col == n - 1:
return 1
total = 0
if row + 1 < m:
total += dfs(row + 1, col)
if col + 1 < n:
total += dfs(row, col + 1)
return total
return dfs(0, 0)