保存递归值以供进一步计算

Question

我必须找出一项任务的不同组合(如何将香料与不同的食物组合(。我用递归得到了解决方案。递归正在工作，J-Unit测试成功。我的问题是，我想存储我的值，这些值是经过计算的，递归不会一次又一次地计算它们。我有哪些机会做到这一点？

这是我当前的代码。

public class FoodCombinations {
public static long tasty(int v, int g) {
if (v == g || v == 1) {
return 1 * 2;
}
return tasty(v - 1, g - 1) + v * tasty(v, g - 1);
}
}

Answer 1

关键词是记忆。

将结果存储在哈希图中，在计算之前进行查找。关于如何同时查找两个参数，有一点复杂，要正确地做到这一点，您必须创建一个包含两个项的小类，实现HashMap(hashCode(或TreeMap(Comparable接口(的要求，并将该类用作键。或者你可以使用一个简单而肮脏的字符串破解：

public class FoodCombinations {
static Map<String, Long> cache = new HashMap<>();
public static long tasty(int v, int g) {
String key = v+"|"+g;
if (cache.containsKey(key)) return cache.get(key);
long result;
if (v == g || v == 1) {
result = 1 * 2;
} else {
result = tasty(v - 1, g - 1) + v * tasty(v, g - 1);
}
cache.put(key, result);
return result;
}
}

Answer 2

我用一个私有方法解决了这个问题。最后看起来与您的解决方案类似，但使用了一个私有方法而不是哈希映射。