forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathlylaminju.py
More file actions
18 lines (14 loc) Β· 711 Bytes
/
lylaminju.py
File metadata and controls
18 lines (14 loc) Β· 711 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
'''
μκ° λ³΅μ‘λ: O(m * n)
- λμ νλ‘κ·Έλλ° ν
μ΄λΈ(dp)μ μ¬μ©νμ¬ κ° μ
μμμ κ²½λ‘ μλ₯Ό ν λ²μ© κ³μ°νλ―λ‘ μκ° λ³΅μ‘λλ 격μμ λͺ¨λ μ
μ λν΄ O(m * n)μ
λλ€.
κ³΅κ° λ³΅μ‘λ: O(m * n)
- dp ν
μ΄λΈμ μ¬μ©νμ¬ λͺ¨λ μ
μ λν κ²½λ‘ μλ₯Ό μ μ₯νλ―λ‘ κ³΅κ° λ³΅μ‘λλ O(m * n)μ
λλ€.
'''
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
# save number of unique paths to each cell
dp = [[1] * n for _ in range(m)]
for row in range(1, m):
for col in range(1, n):
dp[row][col] = dp[row][col - 1] + dp[row - 1][col]
return dp[m - 1][n - 1]