Trong bài toán này, chúng ta được cung cấp một mảng gồm n số và một giá trị nguyên k. Nhiệm vụ của chúng ta là Tìm kích thước tối thiểu có thể có của mảng với các quy tắc cho trước để loại bỏ các phần tử.
Mô tả sự cố - chúng ta cần giảm thiểu số phần tử trong mảng. Bằng cách sử dụng thao tác xóa sau, Số phần tử có thể được xóa cùng một lúc là 3. Việc xóa có thể thực hiện được nếu ba phần tử thỏa mãn hai điều kiện đã cho,
Điều kiện 1 - Ba phần tử phải liền nhau.>
Điều 2 - sự khác biệt giữa hai phần tử lân cận là k, tức là arr [i + 1] =arr [i] + k và arr [i + 2] =arr [i + 1] + k.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
{4, 6, 8, 4, 1, 5 }, k = 2 Đầu ra
3
Giải thích
Có thể thực hiện một thao tác xóa đối với chỉ mục 0, 1, 2.
Phương pháp tiếp cận giải pháp
Vấn đề này hơi khó giải quyết vì có thể có các thao tác xóa gián tiếp có thể được nhìn thấy sau khi thực hiện xong một thao tác xóa. Ví dụ, chúng ta xóa các phần tử ở 5, 6, 7. Sau lần xóa này, mảng mới có thể có các phần tử 3, 4, 5 bây giờ thỏa mãn điều kiện xóa. Những dạng vấn đề như vậy có các bài toán con chồng chéo có thể được giải quyết bằng cách sử dụng phương pháp lập trình động. Đối với điều này, chúng tôi sẽ duy trì một ma trận DP [] để lưu trữ kết quả của các bài toán con để truy cập chúng sau này khi được yêu cầu, điều này được gọi là phép ghi nhớ.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000
int DP[MAX][MAX];
int calcMinSize(int arr[], int start, int end, int k){
if (DP[start][end] != -1)
return DP[start][end];
if ( (end-start + 1) < 3)
return end-start +1;
int minSize = 1 + calcMinSize(arr, start+1, end, k);
for (int i = start+1; i<=end-1; i++){
for (int j = i+1; j <= end; j++ ){
if (arr[i] == (arr[start] + k) && arr[j] == (arr[start] +
2*k) && calcMinSize(arr, start+1, i-1, k) == 0 && calcMinSize(arr, i+1, j- 1, k) == 0) {
minSize = min(minSize, calcMinSize(arr, j+1, end, k));
}
}
}
return (DP[start][end] = minSize);
}
int main() {
int arr[] = {4, 6, 8, 4, 1, 5 };
int n = sizeof(arr)/sizeof(arr[0]);
int k = 2;
memset(DP, -1, sizeof(DP));
cout<<"The minimum possible size of the array after removal is "<<calcMinSize(arr, 0, n-1, k);
return 0;
} Đầu ra
The minimum possible size of the array after removal is 3