[LeetCode] Unique Paths

Problems:

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

Note: m and n will be at most 100.

Solution:O(m)

public class Solution {
    public int uniquePaths(int m, int n) {
        if(m< 0 || n< 0)
            return 0;
     int min = Math.min(m,n);
     int ret = 1;      
      for(int i=0; i<min-1; i++){
          if(ret % (i+1) == 0){
           ret /= (i+1);
           ret *= (m+n-2-i);
          }else{
           ret *= (m+n-2-i);
           ret/=(i+1);
          }
      }    
        return ret;
    }
}

Key Concept: Use math C(m+n-2, m-1)