O(n) solution in Java, 0ms, statistic mathod


  • 0
    Y
    public int uniquePaths(int m, int n) {
        double result = 1;
        if(m>n){
            int temp = n;
            n = m;
            m = temp;
        }
        for(int i=0;i<m-1;i++){
            result = (result*(m+n-2-i))/(i+1);
        }
        return (int)result;
    }
    

    Totally m+n-2 steps. We have to choose m-1 steps as down (or n-1 steps as right, we should choose the smaller one), regardless of the sequence of these m-1 steps..

    Based on statistic knowledge, it will be (m+n-2)!/((m-1)!*(n-1)!).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.