[LeetCode] 062. Unique Paths

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

Unique Paths - LeetCode

 

1. DFS풀이 ( 시간초과 )

class Solution {
public:
    int uniquePaths(int m, int n) {
        result = 0;
        max_y = m-1;
        max_x = n-1;
        DFS(0,0);
        
        return result;
    }
private:
    int result, max_y, max_x;
    
    void DFS(int cur_y, int cur_x)
    {
        // cout << cur_y << "," << cur_x << endl;
        if(cur_y > max_y) return;
        if(cur_x > max_x) return;
        if(cur_x==max_x && cur_y==max_y)
        {
            result++;
            return;
        }
        DFS(cur_y+1, cur_x);
        DFS(cur_y, cur_x+1);
    }
};

시간이 초과되지만 정답은 제대로 나온다. Time Complexity를 계산해야함.

 

2. DP풀이

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

- 0으로 초기화했다가 for 반복문 2번 돌면서 첫 번째 Row와 Col에 1을 할당했는데 처음부터 1을 할당하면 된다 굿.

 

 

3. Permutation

4*4Grid를 가정해보자. 처음 위치에서 오른쪽 끝으로 가려면 오른쪽으로 3번 아래쪽으로 3번 움직여야한다.

RRR DDD

이때 RRR DDD의 Permutation을 구하면 된다. 중복이 있으므로 6! / 3! * 3!를 해준다.

이를 일반화하면 (M-1+N-1)! / (M-1)! (N-1)!

class Solution {
public:
    int uniquePaths(int m, int n)
    {
        if( m==1 || n==1) return 1;
        
        long long result = 1;
        int bigger = m>n? m:n;
        int smaller = m>n? n:m;
        
        for(int i=m+n-2; bigger-1<i; --i)
        { result *= i; }
       
        int divider = 1;
        for(int i=1; i<smaller; ++i)
        { divider *= i; }
    
        return result/divider;
    }
};

더 간단하게 풀이

    int uniquePaths(int m, int n) {
        int A = m + n - 2, 
        int B = std::min(m - 1, n - 1);
        long long result = 1;
        for (int i = 1; i <= B; ++i)
            result = result * A-- / i;
        return (int)result;
    }

 

참고하기

https://leetcode.com/problems/unique-paths/discuss/22954/C%2B%2B-DP

C++ DP - LeetCode Discuss