[LeetCode][Python3] 62. Unique Paths

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]