[LeetCode] 62. Unique Paths 풀이 및 코드

문제 

m*n의 그리드에서 좌측 위 코너에서 우측 아래 코너까지 가는 각기 다른 경로의 개수를 리턴해라.

---

풀이

그리드의 크기와 같은 테이블을 그리고 각 칸마다 그 칸으로 가는 경로의 총 개수를 기입하면 된다. 이 문제를 동적 프로그래밍으로 풀수 있는 이유는 작은 문제를 풀면 이를 이용하여 큰 문제를 풀 수 있기 때문이다.

문제에는 아래나 오른쪽으로 밖에 가지 못한다는 제약 사항이 있기 때문에, 특정 칸까지 가는 경로의 수는 위의 칸까지 가는 경로의 수와 왼쪽 칸까지 가능 경로의 수의 합과 같다.

(어렸을 때 눈높이 학습지를 많이 풀어서 그런지 이 문제가 너무 익숙하다 ㅋㅋㅋ)

---

코드

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

---

리트코드 제출 결과

---

출처

leetcode.com/problems/unique-paths/