Mô tả bài toán
N bạn. Mỗi bạn có thể đơn thân hoặc cặp với một bạn khác (mỗi cặp chỉ 2 người). Đếm số cách chia nhóm.
Ví dụ
N=3 → Output: 4.\nCách: {A}{B}{C}, {A,B}{C}, {A,C}{B}, {A}{B,C}.
Giải thuật (DP)
f(n) = f(n-1) + (n-1)*f(n-2).\n- f(n-1): bạn thứ n đơn thân.\n- (n-1)*f(n-2): bạn n cặp với 1 trong n-1 bạn còn lại, phần còn lại f(n-2).\nCơ sở: f(0)=0, f(1)=1, f(2)=2.
Mã nguồn C++ (DP lặp)
#include <iostream>
using namespace std;
int countGroupPairing(int N) {
vector dp(N+1);
for (int i=0; i<=N; i++) {
if (i<=2) dp[i]=i;
else dp[i] = dp[i-1] + (i-1)*dp[i-2];
}
return dp[N];
}
int main() {
int N=6;
cout << "Number of friends: " << N << '\n';
cout << "Total pairings: " << countGroupPairing(N);
return 0;
} Đầu ra
The number of friends in the group is 6 The total number of possible pairs is 76