LeetCode [62]: Unique Paths

📌 LeetCode [62]: Unique Paths

🔗 문제 링크

---

문제 설명 📄

로봇이 (m \times n) 격자의 왼쪽 위에서 오른쪽 아래로 이동하려고 합니다.
로봇은 오른쪽 또는 아래쪽으로만 이동할 수 있습니다.
격자에서 오른쪽 아래로 가는 데 필요한 고유 경로의 수를 반환하는 문제입니다.

---

문제 접근 방식 📋

1. 동적 계획법(DP) 사용:
   • DP 배열 dp[i][j]는 (i, j)까지의 고유 경로 수를 저장합니다.
2. 초기화:
   • 시작점 (dp[0][0] = 1): 시작점에서의 경로 수는 1입니다.
   • 첫 번째 행과 첫 번째 열은 각각 오른쪽/아래로만 이동 가능하므로 (dp[i][0] = 1), (dp[0][j] = 1)로 초기화됩니다.
3. DP 점화식:
   • 각 셀 (dp[i][j])는 왼쪽에서 오는 경로와 위쪽에서 오는 경로의 합입니다:
     [ dp[i][j] = dp[i-1][j] + dp[i][j-1] ]
4. 결과 반환:
   • DP 배열의 마지막 셀 (dp[m-1][n-1])이 고유 경로의 수를 반환합니다.

---

Solution 💻

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

        for i in range(m):
            for j in range(n):
                up = 0 if i-1 < 0 else dp[i-1][j]
                left = 0 if j-1 < 0 else dp[i][j-1]
                dp[i][j] += up + left

        return dp[m - 1][n - 1]

---

시간 복잡도 분석 ⏲️

• 시간 복잡도: (O(m * n))
  • DP 배열의 모든 셀을 한 번씩 계산.
• 공간 복잡도: (O(m * n))
  • DP 배열이 (m * n)의 공간을 차지.

---