forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathhu6r1s.py
More file actions
23 lines (18 loc) Β· 747 Bytes
/
hu6r1s.py
File metadata and controls
23 lines (18 loc) Β· 747 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
"""
dfsλ‘ νλ©΄ λ κ²μ΄λΌκ³ μκ°μ νμ§λ§ μ΄μ λ¬Έμ μ κ°μ λ°©μμΌ μ€ μμλλ° μ΄λ¬ν λ°©μμ΄ μλ κ²μ μμμ
"""
# def uniquePaths(self, m: int, n: int) -> int:
# def dfs(x, y):
# if x == m - 1 and y == n - 1:
# return 1
# if x >= m or y >= n:
# return 0
# return dfs(x + 1, y) + dfs(x, y + 1)
# return dfs(0, 0)
def uniquePaths(self, m: int, n: int) -> int:
dp = [[1] * n for _ in range(m)]
for row in range(1, m):
for col in range(1, n):
dp[row][col] = dp[row - 1][col] + dp[row][col - 1]
return dp[-1][-1]