我正在制作一個程序，給出給定兩個數字的可能組合數量，比如 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)); }}這個可行，但我需要使用記憶來提高時間復雜度并加快處理較大數字的速度，但我不知道如何去做。我該怎么做呢？
2 回答
當年話下
TA貢獻1890條經驗 獲得超9個贊
n choose k = ( n - 1 choose k - 1) + ( n-1 choose 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];
}
慕妹3146593
TA貢獻1820條經驗 獲得超9個贊
一種方法是進行緩存，這伴隨著內存使用的巨大代價。
public static int combinations(int group, int members) {
if (members > group - members) {
members = group - members; // 21 choose 17 is same as 21 choose 4
}
final int[][] cache = new int[group][members];
return combinations(group, members, cache);
}
private static int combinations(int group, int members, int[][] cache) {
if (cache[group - 1][members - 1] > 0) {
return cache[group - 1][members - 1];
}
else if (members == 1) {
cache[group - 1][members - 1] = group;
return group;
}
else if (members == group) {
cache[group - 1][members - 1] = 1;
return 1;
}
else {
return (combinations(group - 1, members - 1, cache) + combinations(group - 1, members, cache));
}
}
我做了一些快速測試（非專業基準），發現原來的方法需要緩存方法的一半時間?？雌饋硭羞@些對陣列緩存的讀/寫都大大減慢了速度。
另一種方法是改變整個公式。
public static int combinations(int group, int members) {
if (members > group - members) {
members = group - members;
}
int answer = 1;
for (int i = group; i > group - members; i--) {
answer *= i;
}
for (int i = 1; i <= members; i++) {
answer /= i;
}
return answer;
}
再次，我用原始方法測試了新方法（我讓它們BigInteger用于測試），新方法非常快（原始方法為 26 秒，后者為 0.00 秒，35 選擇 15）。
補充一點，我認為使用遞歸調用的時間復雜度為O((group)(log members))，而使用新公式的時間復雜度為O(members)。
添加回答
舉報
0/150
提交
取消