试图解决Leetcode唯一路径问题时数字太大
我正在尝试从LeetCode 解决唯一路径问题。基本上，问题是给您一个mby n网格，并且您必须计算从左上角到右下角的路径数，而仅向下或向右。
我正在做数学方法，要弄清楚这很复杂，但是基本公式是这样的：
(m - 1 + n - 1) choose (min(m - 1, n - 1))，和式为n choose rIS n! / (r! * (n-r)!)。
这种方法效果很好，但是阶乘最终超出了整数限制，因此变为负数。我接下来尝试做的就是将所有内容更改为long，但是随后这些数字又变得太大了。如何简化数字，使其保持在限制之下？这是我的代码：
public int uniquePaths(int m, int n) { // The method being called
return (int) (m == 1 || n == 1 ? 1 : choose((m - 1) + (n - 1), Math.min(m - 1, n - 1)));
}
private long choose(long n, long r) { // Calculated n choose r
return fact(n) / (fact(r) * fact(n - r));
}
private long fact(long n) { // Calculates factorial of n
return n == 1 ? 1 : n * fact(n - 1);
}
我知道可以简化它，因为答案是整数，因此该数字应该很容易归为Long.MAX_VALUE。
问题来源：Stack Overflow
展开
收起
1
条回答
写回答
写回答
-
知道了 我需要做的是消除分母中更大的数字。如果r大于n-r，则公式变为：
n * n-1 * n-2 ... * r+1 / (n-r)!如果n-r大于r，则公式变为：
n * n-1 * n-2 ... * (n-r)+1 / r!这使得分母中更大的数字也越来越n!小。最后是我的代码：
public int uniquePaths(int m, int n) { // Method being called return (int) (m == 1 || n == 1 ? 1 : choose((m - 1) + (n - 1), Math.min(m - 1, n - 1))); } private long choose(long n, long r) { // Calculates n choose r return r > n - r ? fact(n, r) / fact(n - r) : fact(n, n - r) / fact(r); } private long fact(long n) { // Calculates n! return n == 1 ? 1 : n * fact(n - 1); } private long fact(long n, long lower) { // Calculates n! with lower bound of lower; that is n * n-1 * n-2 ... * lower+1. return n == lower ? 1 : n * fact(n - 1, lower); }回答来源：Stack Overflow
2020-03-23 11:13:56赞同 展开评论 打赏
问答标签：
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
问答排行榜
最热
最新
推荐问答
