[LeetCode] 62 | Unique Paths | Python

---

문제 링크: https://leetcode.com/problems/unique-paths/

---

문제

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to $2 \times 10^9$

---

조건

• 1 <= m, n <= 100

---

내 풀이

위 그림을 2d list로 나타내고, 그 list를 grid라 명명하자.

grid[h][w]까지 도달하는 방법의 수는 grid[h-1][w]에서 오는 방법과 grid[h][w-1]에서 오는 방법이 있다.

그렇기 때문에 grid[h][w]까지의 경우의 수는 grid[h-1][w] + grid[h][w-1]이다.

---

코드

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        grid = [[0]*n for _ in range(m)]
        
        for w in range(n):
            grid[0][w] = 1
        
        for h in range(m):
            grid[h][0] = 1
            
        
        for h in range(1, m):
            for w in range(1, n):
                grid[h][w] = grid[h][w-1] + grid[h-1][w]
        
        return grid[m-1][n-1]