Problem :

https://leetcode.com/problems/unique-paths


My Solution :

class Solution:
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
memo = {}

def comb(n, r):
if r == 0 or n == r:
return 1
if r == 1 or n-1 == r:
return n
if (n, r) in memo:
return memo[(n, r)]
memo[(n, r)] = memo[(n, n-r)] = comb(n-1, r-1) + comb(n-1, r)
return memo[(n, r)]

return comb(m+n-2, min(m, n)-1)


Comment :

전형적인 DP 문제인데, 나는 문제를 보는 순간 그냥 단순 조합 문제라고 생각했다. 그래서 m+n-2 중 min(m, n)-1개를 고르는 문제로 풀었다. 물론 math.factorial 을 사용하거나 itertools.combinations를 사용하면 바로 풀린다. (combinations는 큰 수에서 timeout 발생)


하지만 조합을 직접 구현해보는 것에 초점을 맞춰서 위와 같이 풀었다. nCr = n-1Cr-1 + n-1Cr 공식이다.


왜 nCr 조합 문제라고 생각했냐면... 예를 들어 오른쪽으로 7번, 아래쪽으로 3번 움직여야 한다면 총 10번의 움직임 중 아래쪽 3번이 들어갈 자리만 지정하면 끝이다. 즉 10C3 문제라는 뜻이다.


Factorial Example :

class Solution:
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
from math import factorial as fact
return fact(m+n-2) // fact(m-1) // fact(n-1)


아래는 전형적인 DP 방식 Bottom-up 으로 풀이한 것이다.

굳이 말로 풀어쓰자면 예를 들어 (5,3)에 도착하는 경우는 (4,3)에서 온 경우와 (5,2)에서 온 경우밖에 없다. 따라서 두 경우의 수를 더하면 된다.


My Solution2 :

class Solution:
def uniquePaths(self, m, n):
"""
:type m: int
:type n: int
:rtype: int
"""
dp = [[1]*m for _ in range(n)]
for i in range(1, n):
for j in range(1, m):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[-1][-1]