LeetCode(Dynamic Programming)Unique Paths

2018-07-03

Unique Paths

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?

Note: m and n will be at most 100.

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:

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

思路：仔细读题分析后发现其实是一个排列组合问题，我们将机器人向右走记做0，向下走记做1，则在一个mxn的大格子中，我们走到右下角的终点，不管以何种路径走，最后必然有m-1个0和n-1个1。所以问题就转化成了从n+m-2个位置中选择m-1个0或者n-1个1有多少种选法的问题了。

因为int型会溢出，所以用了BigInteger。

代码如下：

import java.math.BigInteger;
class Solution {
    public int uniquePaths(int m, int n) {
         if(m<=0 && n<=0){
             return 0;
         }
         if(m==1 || n==1){
             return 1;
         }
         int total=m+n-2;
         int choose=Math.min(m,n)-1;
         
         BigInteger c=BigInteger.valueOf(total);
         BigInteger b=BigInteger.valueOf(choose);
         
        
         for(int i=1; i<choose; i++){
             int temp=total-i;
             c=c.multiply(BigInteger.valueOf(temp));
             int t=choose-i;
             b=b.multiply(BigInteger.valueOf(t));
             
         }
         BigInteger res=c.divide(b);
         int r=res.intValue();
         return r;
    }
}