組合在Java

Question

使用記憶化我正在計算給定兩個數字，前一個組合的程序：

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

我怎麼能夠使用memoization這個，以便使它更快計算更大的數字？

Answer 1

你可能會更好使用更高效的計算公式：http://en.wikipedia.org/wiki/Binomial_coefficient#Multiplicative_formula

如果你想使用這個公式，那麼這是一種方法，memoize的（沒有我可能有錯別字）：

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