在Java中使用备注组合 [英] Combinations using memoization in java
本文介绍了在Java中使用备注组合的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我正在编写一个程序,计算给定两个数字的组合,例如:
I'm making a program that calculates a combination given two numbers, ex:
java Combination 5 3
给出的答案是10.
我有一个看起来像这样的方法:
I have a method that looks like this:
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);
我该如何使用备忘录来使它以更大的数字更快地进行计算?
How would I be able to use memoization for this in order to make it calculate faster with larger numbers?
推荐答案
使用更有效的公式可能会更好: http://en.wikipedia.org/wiki/Binomial_coefficient#Multiplicative_formula
You might be better off using a more efficient formula: http://en.wikipedia.org/wiki/Binomial_coefficient#Multiplicative_formula
如果您想使用此公式,那么这是一种记忆方式(没有我的错别字):
If you want to use this formula, then this is a way to memoize (sans the typos I might have):
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中使用备注组合的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文