DP2D: 62. Unique Paths

62. Unique Paths

 

문제

62. 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 * 109.

 

Example 1:

Input: m = 3, n = 7
Output: 28

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

 

Constraints:

• 1 <= m, n <= 100

 

문제 설명

 

 

 

Code

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 초기화:
        # row 배열은 마지막 행(아래쪽 행)의 경로 수를 저장합니다.
        # 마지막 행의 모든 칸에서 오른쪽 끝으로 가는 경로는 항상 1이므로,
        # row는 [1, 1, ..., 1]로 초기화됩니다.
        row = [1] * n
        
        # 행을 하나씩 계산합니다 (맨 아래 행 제외). 총 m-1번 반복합니다.
        for i in range(m - 1):  # 현재 행을 계산. i는 반복 횟수 (0부터 시작).
            # 새로운 행의 경로 수를 저장할 newRow를 초기화합니다.
            # 첫 번째 열은 항상 1 (맨 왼쪽 열에서 아래로만 이동 가능하므로 경로 수는 1).
            newRow = [1] * n

            # 오른쪽에서 왼쪽으로 현재 행의 값을 계산합니다.
            # 마지막 두 번째 열부터 첫 번째 열까지 역순으로 순회합니다.
            for j in range(n - 2, -1, -1):
                # 현재 칸의 경로 수 = 오른쪽 칸(newRow[j + 1])의 경로 수 +
                # 아래 행(row[j])의 경로 수
                newRow[j] = newRow[j + 1] + row[j]
            
            # 계산이 끝난 현재 행(newRow)을 row로 업데이트합니다.
            # 이제 row는 현재 행의 경로 수를 저장하며, 다음 반복에서 사용됩니다.
            row = newRow
        
        # 최종적으로 row[0]에는 맨 위 왼쪽에서 맨 아래 오른쪽으로 가는 모든 경로의 수가 저장됩니다.
        return row[0]

# 예제: m = 3, n = 7
# 1. 초기 상태:
#    row = [1, 1, 1, 1, 1, 1, 1]  (맨 아래 행의 경로 수)
#
# 2. 첫 번째 반복 (i = 0):
#    - newRow 초기화: [1, 1, 1, 1, 1, 1, 1]
#    - 오른쪽에서 왼쪽으로 계산:
#      newRow[5] = newRow[6] + row[5] = 1 + 1 = 2
#      newRow[4] = newRow[5] + row[4] = 2 + 1 = 3
#      newRow[3] = newRow[4] + row[3] = 3 + 1 = 4
#      newRow[2] = newRow[3] + row[2] = 4 + 1 = 5
#      newRow[1] = newRow[2] + row[1] = 5 + 1 = 6
#      newRow[0] = newRow[1] + row[0] = 6 + 1 = 7
#    - row 업데이트: row = [7, 6, 5, 4, 3, 2, 1]
#
# 3. 두 번째 반복 (i = 1):
#    - newRow 초기화: [1, 1, 1, 1, 1, 1, 1]
#    - 오른쪽에서 왼쪽으로 계산:
#      newRow[5] = newRow[6] + row[5] = 1 + 2 = 3
#      newRow[4] = newRow[5] + row[4] = 3 + 3 = 6
#      newRow[3] = newRow[4] + row[3] = 6 + 4 = 10
#      newRow[2] = newRow[3] + row[2] = 10 + 5 = 15
#      newRow[1] = newRow[2] + row[1] = 15 + 6 = 21
#      newRow[0] = newRow[1] + row[0] = 21 + 7 = 28
#    - row 업데이트: row = [28, 21, 15, 10, 6, 3, 1]
#
# 4. 최종 결과:
#    row[0] = 28 (맨 위 왼쪽에서 맨 아래 오른쪽으로 가는 고유 경로의 수)

# 출력: 28

참고 문제 풀이

https://youtu.be/IlEsdxuD4lY?si=W1mptQbA_ho9RH7M

 

============================================================================================

 

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 초기 행(row)을 생성. 첫 번째 행의 모든 값은 1로 설정.
        # 이는 각 칸에 도달할 수 있는 유일한 경로가 오른쪽으로만 이동한 경우임을 의미.
        row = [1] * n  # [1, 1, 1, ..., 1] (길이 n)

        # 첫 번째 행은 초기화되었으므로 나머지 m-1개의 행을 계산
        for i in range(m - 1):  # 총 m-1번 반복
            # 새로운 행을 초기화. 첫 번째 열의 값은 항상 1.
            # 이는 해당 열의 모든 경로가 위에서 내려온 경우임을 의미.
            newRow = [1] * n  # [1, 1, 1, ..., 1] (길이 n)

            # 두 번째 열부터 마지막 열까지 계산 (열의 시작은 인덱스 1)
            for j in range(1, n):  # 열은 1부터 n-1까지
                # 현재 위치의 값(newRow[j])은 왼쪽 값(newRow[j-1])과
                # 이전 행(row[j])의 값을 더한 값
                newRow[j] = newRow[j - 1] + row[j]
                # 예: newRow[2] = newRow[1] + row[2]

            # 현재 행(newRow)을 다음 반복에서 이전 행(row)로 사용
            row = newRow

        # 마지막 행의 마지막 값(row[-1])이 최종 결과.
        return row[-1]

 

 

추가 문제들

1. 63. Unique Paths II
2. 64. Minimum Path Sum
3. 174. Dungeon Game

 

이제 그냥 품

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

        for i in range(m):
            grid[i][0] = 1

        for j in range(n):
            grid[0][j] = 1
        
        for i in range(1, m):
            for j in range(1, n):
                grid[i][j] = grid[i-1][j] + grid[i][j-1]

        return grid[m-1][n-1]

 

좀더 최적화

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0] * n for _ in range(m)]

        # dp[m-1][:] = 1 <-- 에러
        dp[m-1] = [1]*n

        for r in range(m-2, -1, -1):
            dp[r][n-1] = 1
            for c in range(n-2, -1, -1):
                dp[r][c] = dp[r+1][c] + dp[r][c+1]

        return dp[0][0]