C++ 62. Unique Paths(Leet Code)

Leet Code_62. Unique Paths

Dynamic Programming

 

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

 

문제 해석

 

이 문제를 풀기위해 이해해야 할 내용은 다음과 같습니다.

 

목표

Start부터 Finish 까지 갈수있는 중복되지 않는 모든 경로 구하기

​

방법

1. Start부터 Finish 까지 갈수있는 중복되지 않는 모든 경로 구하기

 

결과

Start부터 Finish 까지 갈수있는 중복되지 않는 모든 경로 구하기

 

통과한 코드

class Solution {
public:
    int uniquePaths(int m, int n) {
        if(n == 0 && m == 0)
            return 0;
        vector<vector<long long int>> dp(n,vector<long long int>(m,0)); 
        dp[0][0] = 1;
        for(int i = 1; i < m; i++){
            dp[0][i] = dp[0][i-1];
        }
        for(int i = 1; i < n; i++){
            dp[i][0] = dp[i-1][0];
        }
        for(int i = 1; i < n; i++){
            for(int j = 1; j < m; j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[n-1][m-1];
    }
};

오랜만에 경로를 구하는 DP 문제

<i, j>까지의 경로는 <i-1,j>까지 갈수있는 경로와 <i,j-1>까지 갈수있는 경로를 합친것과 같으므로 위의 코드와 같이 해결