Java 0ms solution with explanations.


  • 1
    A

    When we solve this problem, we should keep in mind that this is a permutation and combination problem of high school level. Therefore, we need not to use DP solution or recursive solution.
    Given m and n, there will be m+n-2 steps. Among these m+n-2 steps, n-1 steps are towards right and m-1 steps are towards down.
    So, there will be (m-1)C(m+n-2) solutions, which is the same as (n-1)C(m+n-2). All we need is to write a program quickly calculating (m-1)C(m+n-2) or (n-1)C(m+n-2).

    public int uniquePaths(int m, int n) {
            int num = Math.max(m, n);
            long ans = 1, temp = 1;
            for (int i = m + n - 2, j = 1; i >= num; i--, j++) {
                ans *= i;
                temp *= j;
            }
            return (int)(ans / temp);
        }
    
    >! >! >! >! Spoiler

Log in to reply
 

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