LeetCode(61)UniquePath1

제목은 다음과 같습니다.
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below). How many possible unique paths are there? Above is a 3 x 7 grid. How many possible unique paths are there?
Note: m and n will be at most 100.
분석은 다음과 같습니다.
현재 알고 있는 세 가지 해법, 동적 기획, 배열 조합, 귀속.첫 번째, 동적 기획, 비교적 그리워요.임의의 점(x, y)은 (x, y)의 왼쪽 인접점(x, y-1)에서 오거나 (x, y)의 상접점(x-1, y)에서 온다.만약 f(x, y)로 로봇이 점(x, y)에 도착했을 때의 걸음걸이를 표시한다면 f(x, y)=f(x-1, y)+f(x, y-1).여기서 베이스 조건은 입니다.(x, y)가 맨 윗줄이나 맨 왼쪽 열에 있을 때 로봇이 오른쪽으로 가든지 아래로 가든지 분명히 f(x, y)=1 if(x==1 or y==0)만 갈 수 있다.이 방법의 시간 복잡도는 O(m, n)이고 공간 복잡도는 O(m, n)이다.만약 조금만 최적화한다면 공간의 복잡도는 O(min(m, n))로 낮출 수 있다.다음 코드 보십시오.
두 번째, 배열 조합은 매우 교묘하다. 마침 크랭킹 더 코드 인터뷰 책에서 이런 해법을 보았다.로봇은 (1,1)점에서 (m,n)점까지 걸어갔다.그것은 오른쪽으로 가든지 아래로 가든지 간에 반드시 오른쪽으로 m-1보를 걷고 아래로 n-1보를 걷는다.모두 m-1+n-1보를 걸었다.그러나 서로 다른 주법은 본질이 오른쪽이나 아래로 구성된 m-1+n-1 길이의 서열이 다르다.주법의 총수목은 본질적으로 m-1+n-1개의 총보수에서 m-1개를 골라 오른쪽으로 걷는 주법의 개수를 나타낸다. 이 문제의 또 다른 표현은 주법의 총수목이다. 본질적으로 m-1+n-1개의 총보수에서 n-1개를 골라 아래로 걷는 주법의 개수를 나타낸다.이것은 사실 바로 조합의 작은 성질이다.
C(a+b, a)=C(a+b, b) 이렇게 하면 문제가 하나의 수학 계산으로 바뀌어 C(m-1+n-1, m-1)를 구한다.세 번째, 돌아가는 방법.시간이 좀 걸려서 나는 OJ로 귀환 방법을 제출하려고 했는데 시간이 초과된 것을 발견했다.
내 코드:
4

// version 1      bottom-up
class Solution {
public:
    int uniquePaths(int m, int n) {
        int ** arr = new int* [m];
        for(int i=0;i<m;i++)
            arr[i]=new int[n];
        for(int i=0;i<m;i++)
            arr[i][0]=1;
        for(int i=0;i<n;i++)
            arr[0][i]=1;
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                arr[i][j]=arr[i-1][j]+arr[i][j-1];
            }
        }
        return arr[m-1][n-1];
    }
};

사실 m*n만큼 큰 행렬을 사용할 필요가 없다. O(min(min, n)) 크기의 1차원 수조만 있으면 된다. 이렇게 하면 동적 기획의 공간 복잡도를 다시 최적화할 수 있다.

// version 2      bottom-up       O(m*n)   O(min(m,n));
class Solution {
public:
    int uniquePaths(int m, int n) {
        int s=(m<n)?m:n;
        int l=(m>n)?m:n;
        int * arr= new int [s];
        for(int j=0;j<s;j++)
            arr[j]=1;
        for(int i=1;i<l;i++){
            for(int j=1;j<s;j++){
                arr[j]+=arr[j-1];
            }
        }
        return arr[s-1];
    }
};

// version 3         m-1+n-1     m-1        , C(m-1+n-1, m-1)   。
class Solution {
public:
    unsigned long long  get_factorial(unsigned long long k){ //    
        if(k==0)
            return 1;
        else
            return k*get_factorial(k-1);
    }
    
    int uniquePaths(int m, int n) {
        unsigned long long b=0; //    ， unsigned long long
        unsigned long long c=0;
        if(m<n){ // m-1 n-1         ，      。  C(m+n, n) C(m+n, m)      ，        。
            b=m-1;
            c=n-1;
        }else{
            b=n-1;
            c=m-1;
        }
        unsigned long long res=1;
        unsigned long long keep_b=b;
        while(b>0){
            res*=(b+c);
            b--;
        }
        res=res/get_factorial(keep_b);
        return (int)res;
    }

};

//         。
class Solution {
public:
    int _uniquePaths4(int r, int c, int m, int n) {
        if(r==m-1&&c==n-1) //     ，           。
            return 1;
        if(r>=m||c>=n) ////     ，          ，          。
             return 0;
        return _uniquePaths4(r+1, c,m,n)+_uniquePaths4(r, c+1,m,n);
    }
    int uniquePaths(int m, int n) {
        return _uniquePaths4(0,0, m, n);
    }
};

update: 2014-11-09
배열 조합의 방법을 사용하여 하다.위의 배열 조합 방법과 사고방식은 기본적으로 일치한다.코드가 더 깔끔해요.

class Solution {
private:
    long long cal_factorial(long a, long start = 1) {
        long long res= 1;
        while (a >= start) {
            res *= a;    
            a--;
        }
        return res;
    }
public:
    int uniquePaths(int m, int n) {
        int max_mn = m>n?m:n; //         ，    
        long long a = cal_factorial(m + n - 2, max_mn);
        long long b = cal_factorial(m + n - 2 - max_mn + 1);
        long long result = a/b;
        return result;    
}
};