Cho N và K. Đếm số hoán vị của 1..N có đúng K cặp nghịch đảo (inversion: i < j và a[i] > a[j]).
Ví dụ
Input: N=4, K=1 Output: 3 Hoán vị 4 phần tử: 1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3214, 3241, 3412, 3421, 4123, 4132, 4213, 4231, 4312, 4321 Có 1 nghịch đảo: 1243, 1324, 2134 Input: N=3, K=2 Output: 3 (231, 312, 321)
Phương pháp hiệu quả (Đệ quy + Memoization)
Chèn số N (lớn nhất) vào hoán vị của N-1 số. Nếu chèn ở vị trí cách cuối i vị trí (0-indexed từ phải), sẽ tạo thêm i nghịch đảo mới. Công thức đệ quy:
dp[N][K] = Σ dp[N-1][K-i] với i = 0..min(K, N-1).
Cơ sở: dp[0][*] = 0, dp[*][0] = 1.
Mã nguồn C++
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
int dp[MAX][MAX];
int find_permutations(int N, int K) {
if (N == 0) return 0;
if (K == 0) return 1;
if (dp[N][K] != 0) return dp[N][K];
int result = 0;
for (int i = 0; i <= K; i++) {
if (i <= N - 1)
result += find_permutations(N - 1, K - i);
}
dp[N][K] = result;
return result;
}
int main() {
int N, K;
cin >> N >> K;
cout << find_permutations(N, K);
return 0;
}
Kết quả
0
Lưu ý: Output 0 là do input mẫu không được cung cấp trong code. Với N=4, K=3 → Output 6.
Giải thích
Mảng dp lưu kết quả trung gian (memoization). Hàm đệ quy tính dp[N][K] bằng cách cộng dồn dp[N-1][K-i] cho i từ 0 đến min(K, N-1). Độ phức tạp O(N·K).
Kết luận
Bài viết giải quyết bài toán đếm hoán vị có K nghịch đảo bằng DP đệ quy có nhớ. Độ phức tạp O(N·K). Mã C++ sử dụng mảng 2D lưu memo. Có thể triển khai bằng các ngôn ngữ khác.