使用记忆化/动态编程的 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 选择 k = ( n - 1 选择 k - 1) + ( n-1 选择 k ) 自下而上的动态规划方法是:

dp[n][k] = dp[n-1][k-1] + dp[n-1][k] if n > k 
else if n == k
dp[n][k] = 1
else
dp[n][k] = 0

从n = 1和k = 1开始

dp[1][1] = 1; dp[1][0] = 1; 

然后填充一个二维数组，直到dp[n][k]

就像您的情况一样，也可以通过内存来完成。您的方法可以更改为:

int[][] dp = new int[group][members];

public static int combinations(int group, int members, int[][] dp ) {

    if (members == 1) {
        return group;
    } else if (members == group) {
        return 1;
    }

    if ( dp[group][members] != 0 ) {
       return dp[group][members];
    }

    int first = 0, second = 0;
    if ( members <= group - 1) {
      first = combinations( group - 1, members - 1, dp );
      second = combinations( group - 1, members );
    } else if ( members - 1 <= group - 1 ) {
      first = combinations( group - 1, members - 1, dp );
    }
    dp[group][members] = first + second;

    return dp[group][members];
}