62. Unique Paths

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

Unique Paths - LeetCode

 

임의의 정수 m, n이 주어졌을 때 해당 크기의 가로세로 좌판에서 좌상측부터 우하측까지 도달할 수 있는 유일한 경로의 개수를 반환하는 문제다.

---

1. 특정 지점(i, j)까지 방문할 수 있는 경우의 수는 (i-1, j)와 (i, j-1) 지점 방문 경우의 수의 합이다.

(이걸 안풀어봤으면 어떻게 아나 ㅡㅡ.. )

int uniquePaths(int m, int n) {     vector<vector<int>> dp(m, vector<int>(n, 1));     for (int i = 1; i < m; ++i) {         for (int j = 1; j < n; ++j) {             dp[i][j] = dp[i - 1][j] + dp[i][j - 1];         }     }     return dp[m - 1][n - 1]; }

 

2. 1번은 m * n에 대한 공간 복잡도를 가지는데, 지나간 지점의 좌표는 필요하지 않기 때문에 메모리 사용량을 더 줄일 수 있다.

class Solution { public:     int uniquePaths(int m, int n) {         // 도착 지점인 우하측만 필요하니 진행하고 있는 한 줄만 있어도 된다.         vector<int> vec(n, 1);         for (int i=1; i<m; ++i) {             for (int j=1; j<n; ++j) {                 vec[j] += vec[j - 1];             }         }         return vec[n - 1];     } };

---

---

[Python3]

class Solution:     def uniquePaths(self, m: int, n: int) -> int:         cache = [1 for i in range(n)]         for i in range(1, m):             for j in range(1, n):                 cache[j] += cache[j-1]         return cache[n-1]

---