[LeetCode] 62. Unique Paths

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

Unique Paths - LeetCode

문제 유형 : 다이나믹 프로그래밍

문제 난이도 : Medium

 

문제

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 * 10^9.

 

m*n크기의 격자에 로봇이 있다. 로봇은 처음에 왼쪽 맨 위에 있다. 목적지인 오른쪽 아래 끝까지 가야 한다. 

로봇이 목적지까지 도달하기 위한 가능한 겹치지 않는 경로의 수를 구하시오.

 

풀이

m * n크기의 dp테이블을 만들어서 dp[i][j]가 i-1, j-1위치에 도달하기 위한 경우의 수를 담도록 한다.

i나 j가 0인 경우, 경우의 수가 1이다(쭉 가는경우)

나머지의 경우는, 왼쪽으로 한칸 전의 dp값과 위쪽으로 한칸 전의 dp값을 더해서 저장한다.

마지막 dp[m-1][n-1]은 목적지까지의 경로의 수가 나온다.

 

코드

C++

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp (m, vector<int>(n, 1));

        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(i == 0 || j == 0) {
                    continue;
                } else {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }

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