[Leetcode] 62. Unique Paths 문제풀이

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

Unique Paths - LeetCode

 

문제 내용

로봇이 오른쪽 또는 아래로 한칸씩 이동하는데,

출발점부터 도착점까지 경로의 개수를 구하는 문제

 

Example 1:

Input: m = 3, n = 7

Output: 28

 

문제 풀이

1칸을 이동할 때 어디서 오는지 생각하면 금방 DP식을 구할 수 있다.

Dist[y][x] = Dist[y-1][x]+ Dist[y][x-1]

위에서 아래로 오거나 왼쪽에서 오른쪽으로 가는 경우의 수가 있기 때문에

해당 경우의 수를 더해주면 된다.

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dist(m, vector<int>(n, 0));
        dist[0][0] = 1;
        
        for (int y = 1; y < m; ++y) {
            dist[y][0] = dist[y-1][0];
        }
        for (int x = 1; x < n; ++x) {
            dist[0][x] = dist[0][x-1];
        }
        
        for (int y = 1; y < m; ++y) {
            for (int x = 1; x < n; ++x) {
                dist[y][x] = dist[y-1][x] + dist[y][x-1];
            }
        }
        
        return dist[m-1][n-1];
    }
};