使用记忆化/动态规划的Java组合学
我正在制作一个程序,给出两个数字可能的组合数量,比如N选择K。我有一个递归解决方案,如下所示:
public static int combinations(int group, int members) {
if (members == 1) {
return group;
}
else if (members == group) {
return 1;
}
else {
return(combinations(group - 1, members - 1) +
combinations(group - 1, members));
}
}
这一个是可行的,但我需要使用记忆来提高时间复杂度,并为更大的数字加快速度,我不知道如何去做。我该怎么做呢
# 1 楼答案
一种方法是缓存,这会带来巨大的内存使用成本
我做了一些快速测试(非专业基准测试),发现原来的方法占用了缓存方法一半的时间。看起来所有这些对阵列缓存的读/写操作都大大降低了速度
另一种方法是改变整个公式
再次,我用原始方法测试了新方法(我让他们使用
BigInteger
进行测试),新方法速度惊人(原始方法26秒,后者0.00秒,35-15秒)再加上一点,我认为使用递归调用的时间复杂度是
O((group)(log members))
,而使用新公式只是O(members)
# 2 楼答案
按照
n choose k = ( n - 1 choose k - 1) + ( n-1 choose k )
的公式进行 自下而上的动态规划方法是:从
n = 1
和k = 1
开始然后填充一个二维数组直到
dp[n][k]
它也可以像你的情况那样通过备忘录来完成。您的方法可以更改为: