使用记忆化/动态编程的 Java 组合

Question

我正在制作一个程序，给出给定两个数字的可能组合数量，比如 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));

    }

}

这个可行，但我需要使用记忆来提高时间复杂度并加快处理较大数字的速度，但我不知道如何去做。我该怎么做呢？

Answer 1

n choose k = ( n - 1 choose k - 1)&nbsp; + ( n-1 choose k ) 按照自下而上的动态规划方法的公式 是：dp[n][k] = dp[n-1][k-1] + dp[n-1][k] if n > k&nbsp;else if n == kdp[n][k] = 1elsedp[n][k] = 0从n = 1和开始k = 1dp[1][1] = 1; dp[1][0] = 1;&nbsp;然后填充一个二维数组直到 dp[n][k]也可以像您的情况一样通过记忆来完成。您的方法可以更改为：int[][] dp = new int[group][members];public static int combinations(int group, int members, int[][] dp ) {&nbsp; &nbsp; if (members == 1) {&nbsp; &nbsp; &nbsp; &nbsp; return group;&nbsp; &nbsp; } else if (members == group) {&nbsp; &nbsp; &nbsp; &nbsp; return 1;&nbsp; &nbsp; }&nbsp; &nbsp; if ( dp[group][members] != 0 ) {&nbsp; &nbsp; &nbsp; &nbsp;return dp[group][members];&nbsp; &nbsp; }&nbsp; &nbsp; int first = 0, second = 0;&nbsp; &nbsp; if ( members <= group - 1) {&nbsp; &nbsp; &nbsp; first = combinations( group - 1, members - 1, dp );&nbsp; &nbsp; &nbsp; second = combinations( group - 1, members );&nbsp; &nbsp; } else if ( members - 1 <= group - 1 ) {&nbsp; &nbsp; &nbsp; first = combinations( group - 1, members - 1, dp );&nbsp; &nbsp; }&nbsp; &nbsp; dp[group][members] = first + second;&nbsp; &nbsp; return dp[group][members];}

Answer 2

一种方法是进行缓存，这伴随着内存使用的巨大代价。public static int combinations(int group, int members) {&nbsp; &nbsp; if (members > group - members) {&nbsp; &nbsp; &nbsp; &nbsp; members = group - members; // 21 choose 17 is same as 21 choose 4&nbsp; &nbsp; }&nbsp; &nbsp; final int[][] cache = new int[group][members];&nbsp; &nbsp; return combinations(group, members, cache);}private static int combinations(int group, int members, int[][] cache) {&nbsp; &nbsp; if (cache[group - 1][members - 1] > 0) {&nbsp; &nbsp; &nbsp; &nbsp; return cache[group - 1][members - 1];&nbsp; &nbsp; }&nbsp; &nbsp; else if (members == 1) {&nbsp; &nbsp; &nbsp; &nbsp; cache[group - 1][members - 1] = group;&nbsp; &nbsp; &nbsp; &nbsp; return group;&nbsp; &nbsp; }&nbsp; &nbsp; else if (members == group) {&nbsp; &nbsp; &nbsp; &nbsp; cache[group - 1][members - 1] = 1;&nbsp; &nbsp; &nbsp; &nbsp; return 1;&nbsp; &nbsp; }&nbsp; &nbsp; else {&nbsp; &nbsp; &nbsp; &nbsp; return (combinations(group - 1, members - 1, cache) + combinations(group - 1, members, cache));&nbsp; &nbsp; }}我做了一些快速测试（非专业基准），发现原来的方法需要缓存方法的一半时间。看起来所有这些对阵列缓存的读/写都大大减慢了速度。另一种方法是改变整个公式。public static int combinations(int group, int members) {&nbsp; &nbsp; if (members > group - members) {&nbsp; &nbsp; &nbsp; &nbsp; members = group - members;&nbsp; &nbsp; }&nbsp; &nbsp; int answer = 1;&nbsp; &nbsp; for (int i = group; i > group - members; i--) {&nbsp; &nbsp; &nbsp; &nbsp; answer *= i;&nbsp; &nbsp; }&nbsp; &nbsp; for (int i = 1; i <= members; i++) {&nbsp; &nbsp; &nbsp; &nbsp; answer /= i;&nbsp; &nbsp; }&nbsp; &nbsp; return answer;}再次，我用原始方法测试了新方法（我让它们BigInteger用于测试），新方法非常快（原始方法为 26 秒，后者为 0.00 秒，35 选择 15）。补充一点，我认为使用递归调用的时间复杂度为O((group)(log members))，而使用新公式的时间复杂度为O(members)。