ในปัญหานี้ เราได้รับอาร์เรย์ของตัวเลข n และค่าจำนวนเต็ม k ภารกิจของเราคือค้นหาขนาดต่ำสุดที่เป็นไปได้ของอาร์เรย์ด้วยกฎที่กำหนดสำหรับการลบองค์ประกอบ
คำอธิบายปัญหา − เราจำเป็นต้องลดจำนวนองค์ประกอบในอาร์เรย์ให้เหลือน้อยที่สุด โดยใช้การดำเนินการลบตาม จำนวนขององค์ประกอบที่สามารถลบออกได้ในครั้งเดียวคือ 3 การลบนั้นเป็นไปได้หากองค์ประกอบทั้งสามตรงตามเงื่อนไขสองเงื่อนไขที่กำหนด
เงื่อนไขที่ 1 − สามองค์ประกอบควรอยู่ติดกัน>
เงื่อนไขที่ 2 − ความแตกต่างระหว่างสององค์ประกอบที่อยู่ใกล้เคียงคือ k นั่นคือ arr[i + 1] =arr[i] + k และ arr[i+2] =arr[i+1] + k
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
{4, 6, 8, 4, 1, 5 }, k = 2 ผลลัพธ์
3
คำอธิบาย
สามารถดำเนินการลบได้หนึ่งครั้งสำหรับดัชนี 0, 1, 2
แนวทางการแก้ปัญหา
ปัญหานี้แก้ไขได้ยากเล็กน้อย เนื่องจากอาจมีการดำเนินการลบโดยอ้อม ซึ่งสามารถมองเห็นได้หลังจากดำเนินการลบเพียงครั้งเดียว ตัวอย่างเช่น เราลบองค์ประกอบที่ 5, 6, 7 หลังจากการลบนี้ อาร์เรย์ใหม่อาจมีองค์ประกอบ 3, 4, 5 ที่ตอนนี้ตรงตามเงื่อนไขสำหรับการลบ ปัญหาประเภทดังกล่าวที่มีปัญหาย่อยที่ทับซ้อนกันสามารถแก้ไขได้โดยใช้แนวทางการเขียนโปรแกรมแบบไดนามิก สำหรับสิ่งนี้ เราจะรักษาเมทริกซ์ DP[] เพื่อเก็บผลลัพธ์ของปัญหาย่อยเพื่อเข้าถึงในภายหลังเมื่อจำเป็น ซึ่งเรียกว่าการท่องจำ
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#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;
} ผลลัพธ์
The minimum possible size of the array after removal is 3
