62. Unique Paths

Backtracking

class Solution {
    int count = 0;

    public int uniquePaths(int m, int n) {
        backtracking(0, 0, m, n);
        return count;
    }

    private void backtracking(int x, int y, int m, int n) {
        if (x == m - 1 && y == n - 1) {
            count++;
            return;
        }

        // go down
        if (x + 1 < m) {
            backtracking(x + 1, y, m, n);
        }

        // go right
        if (y + 1 < n) {
            backtracking(x, y + 1, m, n);
        }
    }
}

Remarks:

1. TC: $O(2^{m+n})$, time limit exceeded for big inputs; SC: $O(1)$.

Math (Combination) OPTIMIZED

class Solution {
    public int uniquePaths(int m, int n) {
        return (int) comb(m + n - 2, Math.min(m - 1, n - 1));
    }

    private long comb(int total, int pick) {
        long res = 1;
        for (int i = 1; i <= pick; i++) {
            res = res * (total - i + 1) / i;
        }
        return res;
    }
}

Remarks:

1. The idea is: from $(0,0)$ to $(m-1, n-1)$, we only need to take $(m-1)$ steps of going “down” and $(n-1)$ steps of going “right”. So actually we are just trying to figure out the combination of selecting $(m - 1)$ steps of going down, out of $(m - 1) + (n - 1)$ steps in total, that is $C(m+n-2, m-1) = \cfrac{(m+n-2)!}{(m-1)!(n-1)!}$.
2. TC: $O(\min(m,n))$, SC: $O(1)$.

Dynamic Programming

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];

        // first row and column all 1
        for (int i = 0; i < m; i++) dp[i][0] = 1;
        for (int j = 0; j < n; j++) dp[0][j] = 1;

        // calculate from (1,1)
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }

        return dp[m - 1][n - 1];
    }
}

Remarks:

1. Idea: each block’s path count is the sum of the one on the top of it and left of it, $dp[i][j] = dp[i-1][j] + dp[j][j-1]$.
2. TC: $O(m\times n)$, SC: $O(m\times n)$.