[C++] LeetCode : Unique Paths

Question

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.

 

m x n 그리드에 로봇이 있습니다. 로봇은 처음에 왼쪽 상단 모서리(즉, grid [0][0])에 있습니다. 로봇은 오른쪽 하단 모서리(즉, grid[m - 1][n - 1])로 이동하려고 합니다. 로봇은 어느 시점에서든 아래로 또는 오른쪽으로만 이동할 수 있습니다. 두 개의 정수 m과 n이 주어지면 로봇이 오른쪽 하단 모서리에 도달하기 위해 취할 수 있는 고유한 경로의 수를 반환합니다. 테스트 케이스는 답이 2 * 109보다 작거나 같도록 생성됩니다.

예시 1

제약사항

• 1 <= m, n <= 100

---

Solution

가능한 최선의 수행 시간(Best Conceivable Runtime(BCR)

• 모든 구간을 한번씩은 훑어야 하기 때문에 O(mn)이다

고려사항

 

---

Solution1 (Dynamic Programming)

2차원 배열을 두고 각 셀에 도착하기 위한 방법을 점진적으로 쌓아가는 것이 가장 기본적으로 널리 쓰이는 방식이다. 최초 행과 열에 도착하는 방법은 1가지뿐이기에 모두 1로 채워주고, 나머지 셀의 가는 방법은 위에서 오는 방법 + 왼쪽에서 오는방법 이기 때문에 둘을 더해준다. 이런 식으로 마지막까지 채워주면 된다. 

class Solution {
public:
    int uniquePaths(int m, int n) {
        int map[100][100] = {0};
        
        for(int i=0; i<m; i++) map[i][0] = 1;
        for(int i=0; i<n; i++) map[0][i] = 1;
        
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                map[i][j] = map[i-1][j] + map[i][j-1];
            }
        }
        
        return map[m-1][n-1];
    }
};

• Time complexity : O(mn) 
• Space Complexity : O(n²) 

출처 : Explore - LeetCode

Explore - LeetCode