1

私は2つの数を与えられた組み合わせを計算するプログラムを作っています、例：

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);

数値が大きいほど計算を高速化するために、メモ化をどのように使用できますか？

4

1 に答える 1

2

より効率的な式を使用する方がよい場合があります: 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;
}
于 2012-10-08T00:40:18.263 に答える