java - 二项式系数。递归树。如何避免多次计算相同的值

Question

我正在使用名为BinomialCoefficients的程序。

我在 C(5,3) 上进行了框跟踪，它返回 10 这是正确的，但我注意到在 的完整递归树中C(5, 3)，值 C(3, 2) 被评估 2 次，C(2, 1) 被评估 3 次。

可以进行哪些修改以避免多次计算相同的值？

这里只是显示上下文的函数。

public static int C(int n, int k) {
   if(k>n)
      return 0;
   else if(k==0 || k==n)
      return 1;
   else
      return C(n-1, k-1)+C(n-1, k);
  }

Answer 1

一项修改是使用 multiplicative formula 。但你必须考虑整数溢出......(编辑:看看@ajb在评论中说了什么)

我建议使用 Map 来缓存结果:

Map<String, Integer> cache = new HashMap<>();    

public static int C(int n, int k) {
  String cacheKey=key(n,k);
  if (cache.containsKey(cacheKey){
    return cache.get(cacheKey);
  if(k>n)
    return 0;
  else if(k==0 || k==n)
    return 1;
  else {
    int result = C(n-1, k-1)+C(n-1, k);
    cache.put(cacheKey, result);
    return result ;
}

public String key(int n, int k){
  return n +"_"+k;
}

当然，使用字符串作为键并不是最有效的方法，但我猜它仍然比一遍又一遍地重新计算相同的值要快得多。