62. Unique Paths.md

62. Unique Paths

---

leetcode Daily Challenge on June 29, 2020.

leetcode-cn Daily Challenge on December 9th, 2020.

---

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 7 x 3 grid. How many possible unique paths are there?

Example 1:

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 -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right

Example 2:

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

Constraints:

• 1 <= m, n <= 100
• It's guaranteed that the answer will be less than or equal to 2 * 10 ^ 9.

---

Solution

• mine
  • Java

    • Recursion Time Limit Exceeded 😥

      // O(2^S)time O(M)space
      // S is Math.min(m,n)
      public int uniquePaths(int m, int n) {
          return path(1, 1, m, n);
      }
      
      public int path(int sx, int sy, int ex,int ey){
          if(sx == ex || sy == ey){
              return 1;
          }
          return path(sx, sy + 1, ex, ey) + path(sx + 1, sy, ex, ey);
      }
      

    • Dynamic Programming

      Runtime: 0 ms, faster than 100.00%, Memory Usage: 36.4 MB, less than 32.05% of Java online submissions

      // O(T)time O(T)space
      // T = m * n
      public int uniquePaths(int m, int n) {
          //f(i,j) = f(i-1,j) + f(i , j - 1);
          int[][]  res = new int[m][n];
          for(int i = 0; i < m; i++){
              Arrays.fill(res[i], 1);
          }
          for(int i = 1; i < m; i++){
              for(int j = 1; j < n; j++){
                  res[i][j] = res[i - 1][j] + res[i][j-1];
              }
          }
          return res[m - 1][n - 1];
      }
      

---

• the most votes

  • Math

    Runtime: 0 ms, faster than 100.00%,Memory Usage: 33 MB, less than 5.10% of Java online submissions

    //O(m)time O(1)space
    public int uniquePaths(int m, int n) {
        int N = n + m - 2;// how much steps we need to do
        int k = m - 1; // number of steps that need to go down
        double res = 1;
        // here we calculate the total possible path number 
        // Combination(N, k) = n! / (k!(n - k)!)
        // reduce the numerator and denominator and get
        // C = ( (n - k + 1) * (n - k + 2) * ... * n ) / k!
        for (int i = 1; i <= k; i++)
            res = res * (N - k + i) / i;
        return (int)res;
    }
    

---