Leetcode-62:Unique Paths

PPLongAbout 2 min

Unique Paths

Info

Description

Topics

Companies

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

Example 1:

Input: m = 3, n = 7
Output: 28

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

Constraints:

1 <= m, n <= 100

Thinking

Only go right or down.
Total steps(right & down) count won’t change.
Combinations? ✅
How DP works?

Solution

Math (Half)

Wrong Solution

Overflow of Combination

There is a great possibility of overflow for int/long numbers when we act by the Combination formula.

C_{m}^{n} = \frac{m!}{n! (m - n)!} = \frac{m (m - 1) (m - 2) (m - n + 1)}{n!}

’Casue n! may cause overflow.(Even long type can not solve.)

That’s what I’d done when first try.

class Solution {
    public int uniquePaths(int m, int n) {
        if (n == 1 || m == 1) {
            return 1;
        }
        int sum = n + m - 2;
        return cMultiple(sum, n - 1);
    }

    public int multiple(int n ) {
        int res = 1;
        while (n > 0) {
            res *= n;
            n--;
        }
        return res;
    }

    public int cMultiple(int m, int n) {
        return multiple(m) / (multiple(n) * multiple(m - n));
    }
}

Correct Example

We divice the mupltiple and division steps from whole to each single step, both combined one divsion and muptiple action.

So we can avoid overflow exception.

C_{m + n - 2}^{m - 1} = \frac{(m + n - 2) (m + n - 3) . . . n}{(m - 1)!}

class Solution {
    public int uniquePaths(int m, int n) {
        long ans = 1;
        for (int x = n, y = 1; y < m; ++x, ++y) {
            ans = ans * x / y;
        }
        return (int) ans;
    }
}

// Author：力扣官方题解
// Link：https://leetcode.cn/problems/unique-paths/solutions/514311/bu-tong-lu-jing-by-leetcode-solution-hzjf/

Time-Complexity: O(min(m, n)) (Can optimize)

Zone-Complexity: O(1)

Why dividable?

Why it’s alwasys get a Integer by this way?

DP (Copy)

Using DP idea:

F[i][j]: Total possible paths to achieve current point.

F[i][0] = F[0][j] = 1

F [i] [j] = F [i - 1] [j] + F [i] [j - 1]

Cause we can only make right or down action.

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] f = new int[m][n];
        for (int i = 0; i < m; ++i) {
            f[i][0] = 1;
        }
        for (int j = 0; j < n; ++j) {
            f[0][j] = 1;
        }
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                f[i][j] = f[i - 1][j] + f[i][j - 1];
            }
        }
        return f[m - 1][n - 1];
    }
}