[LeetCode] 62. Unique Paths

접근

• 완전탐색으로 풀 수 있지만 DP로 푸는 것이 맞는 문제
• Bottom-Up으로 풀 수 있는 지 확인해 보았지만 목적지에서 부터 출발지로 가는 경우의 수를 특정할 수 없음
• 따라서 Top-Down 방식으로 솔루션을 작성하여 해결

예제 1의 DP)

 

문제 링크

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

 

솔루션

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:

        if m == 1 or n == 1:
            return 1

        DP = [[1 for _ in range(n)] for _ in range(m)]
        
        for M in range(1, m):
            for N in range(1, n):
                DP[M][N] = DP[M-1][N] + DP[M][N-1]
        
        return DP[m-1][n-1]