### 题目

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?

### 数学解决问题，排列组合公式

C(n,m) = n! / (m! * (n-m)!)

#### 代码

import java.math.BigDecimal;

public class Solution {
public int uniquePaths(int m, int n) {
if (m <= 0 || n <= 0) { return 0; }
if (m == 1 || n == 1) { return 1; }
int big = Math.max(m-1,n-1);
int small = Math.min(m-1,n-1);
BigDecimal numerator = fromTo(big+1,big+small);
BigDecimal denominator = factorial(small);
return numerator.divide(denominator).intValue();
}
//左右闭区间，例如from=8, to=8. 就等于8.
public BigDecimal fromTo(int from, int to) {
BigDecimal small = new BigDecimal(from);
BigDecimal big = new BigDecimal(to);
BigDecimal res = new BigDecimal(1);
for (int i = from; i <= to; i++) {
res = res.multiply(new BigDecimal(i));
}
return res;
}
// long范围太小，差不多20!的阶乘就超过long的取值范围
public BigDecimal factorial(int n) {
BigDecimal fac = new BigDecimal(1);
for (int i = 1; i <= n; i++) {
fac = fac.multiply(new BigDecimal(i));
}
return fac;
}
}


#### 结果

BigDecimal的效率有限。

### 数学上做了点简化

C(8,5)为例，分母上下的部分数字可以抵消，减小了计算量。

1 * 2 * 3 * 4 * 5 * 6 * 7 * 8
------------------------------------------
1 * 2 * 3 * 4 * 5                   #除法（可抵消）
1 * 2 * 3                           #除法
------------------------------------------
6 * 7 * 8 / 1 / 2 / 3


#### 代码

import java.math.BigDecimal;

public class Solution {
public int uniquePaths(int m, int n) {
if (m <= 0 || n <= 0) { return 0; }
if (m == 1 || n == 1) { return 1; }
int big = Math.max(m-1,n-1);
int small = Math.min(m-1,n-1);
BigDecimal res = new BigDecimal(1);
for (int i = 1; i <= small; i++) {
res = res.multiply(new BigDecimal(big+i)).divide(new BigDecimal(i));
}
return res.intValue();
}
}


### 直接用int

#### 代码

public class Solution {
public int uniquePaths(int m, int n) {
if (m <= 0 || n <= 0) { return 0; }
if (m == 1 || n == 1) { return 1; }
int big = Math.max(m-1,n-1);
int small = Math.min(m-1,n-1);
long res = 1;
for (int i = 1; i <= small; i++) {
res = res * (big+i) / i;
}
return (int)res;
}
}


### 普通递归展开，指数级复杂度

#### 代码

public class Solution {
public int uniquePaths(int m, int n) {
if (m <= 0 || n <= 0) { return 0; }
int[] count = new int[]{ 0 };
recursive(m,n,count);
return count[0];
}
public void recursive(int m, int n, int[] count) {
if (m == 1 && n == 1) { count[0]++; } // reach the end
if (m > 1) { recursive(m-1, n, count); }
if (n > 1) { recursive(m,n-1,count); }
}
}


### 动态规划

#### 代码

public int uniquePaths(int m, int n) {
if (m <= 0 || n <= 0) { return 0; }
int[][] memo = new int[m+1][n+1];
return dp(m,n,memo);
}
public int dp(int m, int n, int[][] memo) {
if (memo[m][n] != 0) { return memo[m][n]; }
if (m == 1 && n == 1) {
memo[1][1] = 1; return 1;
}
int rightCount = 0, downCount = 0;
if (m > 1) { rightCount = dp(m-1,n,memo); }
if (n > 1) { downCount = dp(m,n-1,memo); }
memo[m][n] = rightCount + downCount;
return memo[m][n];
}