Đếm số cách ghép cặp khi mỗi người tối đa 1 bạn C++

Cho N người tham gia. Mỗi người có thể ghép cặp với tối đa 1 người khác, hoặc ở một mình. Đếm số cách phân chia.

Ví dụ minh họa

Ví dụ 1:

• Input: persons = 3
• Output: 4
• Giải thích: (a,b)+(c), (a,c)+(b), (b,c)+(a), (a)+(b)+(c).

Ví dụ 2:

• Input: persons = 2
• Output: 2
• Giải thích: (a,b), (a)+(b).

Công thức đệ quy

Gọi f(n) = số cách với n người.

• f(0) = 1 (rỗng)
• f(1) = 1 (chỉ ở 1 mình)
• f(n) = f(n-1) + (n-1) × f(n-2)

Giải thích: Người thứ n có 2 lựa chọn:

1. Ở một mình: còn n-1 người → f(n-1) cách.
2. Ghép cặp với 1 trong (n-1) người còn lại: chọn bạn (n-1 cách), còn n-2 người → (n-1)×f(n-2) cách.

Mã nguồn C++ (Đệ quy)

#include <iostream>
using namespace std;

int makePairs(int p) {
    if (p == 0 || p == 1) return 1;
    return makePairs(p - 1) + (p - 1) * makePairs(p - 2);
}

int main() {
    int persons = 5;
    cout << "So cach phan chia: " << makePairs(persons);
    return 0;
}

Kết quả chạy chương trình

So cach phan chia: 26

Tối ưu hóa O(n) - Quy hoạch động (DP)

Đệ quy có tính chồng chéo subproblems. Dùng mảng dp[]:

#include <bits/stdc++.h>
using namespace std;

long long makePairsDP(int n) {
    if (n <= 1) return 1;
    vector dp(n + 1);
    dp[0] = dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + (i - 1) * dp[i - 2];
    }
    return dp[n];
}

Dãy số này là gì?

Đây là số điện thoại (Telephone numbers) hoặc số involution (OEIS A000085): 1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, ...

Độ phức tạp

Công thức đóng (xấp xỉ)

f(n) ~ nⁿᐟ² e^(-n/2 + √n - 1/4) / √2 (phức tạp, ít dùng).