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.

public class Solution { public int uniquePaths(int m, int n) { //Note: robot move right || down int N = m + n - 2; //total step int x = m - 1; //res = (N choose x) = N*(N-1)*...*(N-x+1)/x! double res = 1; for (int i = 1; i <= x; i++) { //a single (N-x+i)/i could be non-integer res = res*(N-x+i)/i; } return (int)res; } }

Advertisements