排列组合思路 横着需要走n-1步，竖着需要走m-1步。一共需要走m+n-2步，结果就是或者。 就是m+n-2步中找出m-1来竖着走，剩下的横着走。 这里涉及到计算阶乘，12的阶乘约4亿多，13的阶乘约62亿多，题目m和n最大是100，所以这里计算阶乘需要使用大数类。
代码：
public int uniquePaths(int m, int n) { return factorial(m + n - 2).divide(factorial(m - 1).multiply(factorial(n - 1))).intValue(); } private BigInteger factorial(int x) { BigInteger bi = new BigInteger("1"); for (int i = 1; i <= x; i++) { bi = bi.multiply(BigInteger.valueOf(i)); } return bi; }DP思路：每个格子的值等于其上面一个和左面一个的和。 代码：
public int uniquePaths(int m, int n) { int[][] path = new int[m][n]; for (int i = 0; i < n; i++) path[0][i] = 1; for (int i = 0; i < m; i++) path[i][0] = 1; for (int i = 1; i < n; i++) { for (int j = 1; j < m; j++) { path[j][i] = path[j - 1][i] + path[j][i - 1]; } } return path[m - 1][n - 1]; } 或者 public int uniquePaths(int m, int n) { int[] path = new int[m]; for (int i = 0; i < m; i++) path[i] = 1; for (int i = 1; i < n; i++) { for (int j = 1; j < m; j++) { path[j] += path[j-1] } } return path[m-1]; } 或者golang: func uniquePaths(m, n int) int { path := make([]int, m) for i := range path { path[i] = 1 } for i := 1; i < n; i++ { for j := 1; j < m; j++ { path[j] += path[j-1] } } return path[m-1] }