题解 | JAVA 数学 #求路径# [P3]

DP解

import java.util.*;

public class Solution {
    public int uniquePaths (int m, int n) {
      int[][] mem = new int[m][n];
      // fill first row/col with 1
      Arrays.fill(mem[0], 1);
      for (int[] row : mem) row[0] = 1;
      
      for (int r = 1; r < m; r++) {
        for (int c = 1; c < n; c++) {
          mem[r][c] = mem[r-1][c] + mem[r][c-1];
        }
      }
      
      return mem[m-1][n-1];
    }
}

数学解 C(m+(n-1)-1, n-1)
具体为什么去看精华贴 这里就提供个java不overflow的implementation

import java.util.*;
import java.math.BigInteger;

public class Solution {
    public int uniquePaths (int m, int n) {
      if (m == 1 || n == 1) return 1;
      // C(m+(n-1)-1, n-1)
      //   = [(m+n-2)*...*n] / [(m-1)* ... *1]
      BigInteger numerator = BigInteger.valueOf(1);
      for (int i = n; i <= m+n-2; i++) {
        numerator = numerator.multiply(BigInteger.valueOf(i));
      }
      BigInteger denominator = BigInteger.valueOf(1);
      for (int i = 1; i <= m-1; i++) {
        denominator = denominator.multiply(BigInteger.valueOf(i));
      }
      return numerator.divide(denominator).intValue();
    }
}