[Leetcode] 62. Unique Paths

Identifying the Problem

m x n인 행렬의 왼쪽 위에서 오른쪽 아래로 가는 최단 경로의 개수를 구한다.

Organizing thoughts

보자마자 고등학교 확통 경우의 수 문제임을 알고, 똑같은 풀이를 생각했다.

풀이법은 간단하다.

기준점의 행과 열로 가는 경우의 수는 모두 1이고

나머지 칸들은 칸 기준 왼쪽 칸으로 가는 경우의 수와 위 칸으로 가는 경우의 수의 합이다.

 

예를 들어 2 x 3 이라면,

 

1	1	1
1	1+1 = 2	2+1 = 3

이렇게 된다.

 

따라서

1. 2 x 3 행렬을 하나 만들고

2. 2 x 3 행렬을 모두 1로 초기화

3. dp[1][1] 부터 dp[n-1][n-1]까지 대각선(왼쪽 , 위) 합을 구한다.

4. dp[n-1][n-1] 을 리턴한다.

 

 

Sourcecode

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m,vector<int>(n,1)); // m x n 인 2차원 벡터 행렬 선언
        
        for(int i = 1; i<m; i++)
            for(int k = 1; k<n; k++)
                    dp[i][k] = dp[i][k-1] + dp[i-1][k]; //대각합을 구하는 과정
        
        return dp[m-1][n-1];
    }
};