我正在编写一个程序来计算给定两个数字的组合,例如:
java Combination 5 3
答案是 10。
我有一个如下所示的方法:
public static int choose(int n, int k) { // chooses k elements out of n total
if (n == 0 && k > 0)
return 0;
else if (k == 0 && n >= 0)
return 1;
else return choose(n - 1, k - 1) + choose(n - 1, k);
我如何能够为此使用内存功能,以使其对更大的数字进行更快的计算?
最佳答案
您可能最好使用更有效的公式:http://en.wikipedia.org/wiki/Binomial_coefficient#Multiplicative_formula
如果您想使用这个公式,那么这是一种内存方法(没有我可能有的拼写错误):
private static Map<Pair<Integer, Integer>, Long> cache = new HashMap<>(); // you'll need to implement pair
public static int choose(int n, int k) {
... // the base cases are the same as above.
} else if (cache.contains(new Pair<>(n, k)) {
return cache.get(new Pair<>(n, k));
} else {
Long a = cache.get(new Pair<>(n - 1, k - 1));
if (a == null) { a = choose(n - 1, k - 1); }
Long b = cache.get(new Pair<>(n - 1, k));
if (b == null) { b = choose(n - 1, k); }
cache.put(new Pair<>(n, k), a + b);
return a + b;
}
关于java - 在java中使用记忆化的组合,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12774025/