หาขนาดอาร์เรย์น้อยสุดหลังลบตามกฎด้วย C++

ภาพรวมปัญหา

ได้รับอาร์เรย์และ k ลบได้ 3 ตัวติดกันถ้า: arr[i+1]=arr[i]+k และ arr[i+2]=arr[i+1]+k (Arithmetic Progression ความต่าง k)

หาขนาดน้อยสุดหลังลบซ้ำได้เรื่อยๆ

ตัวอย่าง

อินพุต

{4, 6, 8, 4, 1, 5}, k = 2

เอาต์พุต

3

คำอธิบาย

ลบ 4,6,8 (index 0,1,2) → เหลือ {4,1,5} ขนาด 3

วิธีแก้ปัญหา

Dynamic Programming with Memoization

DP[start][end] = ขนาดน้อยสุดของ subarray start...end

Transition: ลองลบ triplet (start, i, j) ที่เป็น AP diff k และส่วนกลางลบหมดได้

โค้ดตัวอย่าง

#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 << "Minimum possible size after removals: " << calcMinSize(arr, 0, n - 1, k);
    return 0;
}

เอาต์พุต

Minimum possible size after removals: 3

สรุป

DP บน Interval เก็บผลลัพธ์ subproblem ป้องกันการคำนวณซ้ำ Complexity O(N³) ในกรณีแย่ที่สุด