Cho mảng số nguyên dương phân biệt. Tìm tập con lớn nhất sao cho với mọi cặp, phần tử lớn chia hết phần tử nhỏ. Ví dụ:
Input: {1,4,2,6,7} → Output: 1 2 4
Giải thích: Các tập con: (1,2,4), (1,2,6), (1,7)... có 2 tập con độ dài 3.
Input: {1,2,3,6} → Output: 6 2 1
Phương pháp giải
Đệ quy (chậm)
Thử bao gồm/bỏ qua từng phần tử, kiểm tra điều kiện chia hết. O(2ⁿ).
Quy hoạch động (hiệu quả)
- Sắp xếp mảng tăng dần.
- dp[i] = độ dài tập con chia hết lớn nhất kết thúc tại i. Khởi tạo dp[i]=1.
- prev[i] = chỉ số phần tử trước trong tập con tối ưu.
- Với mỗi i, tìm j dp[i].
- Truy vết từ chỉ số có dp max.
Ví dụ minh họa
#include <bits/stdc++.h>
using namespace std;
int main() {
int nums[] = {1,2,3,6};
int n = sizeof(nums)/sizeof(int);
sort(nums, nums+n);
vector<int> prev(n, -1), dp(n, 1);
int max_len = 1, max_idx = 0;
for (int i=1; i<n; i++) {
for (int j=0; j<i; j++) {
if (nums[i] % nums[j] == 0 && dp[i] < dp[j] + 1) {
dp[i] = dp[j] + 1;
prev[i] = j;
}
}
if (max_len < dp[i]) { max_len = dp[i]; max_idx = i; }
}
cout << "Tập con chia hết lớn nhất: ";
for (int k=max_idx; k!=-1; k=prev[k])
cout << nums[k] << " ";
return 0;
}
Kết quả
Tập con chia hết lớn nhất: 6 2 1
Kết luận
Đã giải bài toán tập con chia hết lớn nhất bằng DP sau khi sắp xếp, độ phức tạp O(n²). Code C++ chuyển được sang C, Java, Python. Hy vọng hữu ích.