সি++-এ প্যালিনড্রোমিক সাবলিস্ট মুছে ফেলতে অপারেশন সংখ্যা গণনার প্রোগ্রাম

সমস্যা বিবরণ

একটি সংখ্যার তালিকা nums দেওয়া আছে। একটি অপারেশনে যেকোনো প্যালিনড্রোমিক সাবলিস্ট মুছে ফেলা যায়। পুরো লিস্ট খালি করার জন্য ন্যূনতম অপারেশন সংখ্যা বের করতে হবে।

উদাহরণ: nums = [6, 2, 4, 4, 2, 10, 6] হলে আউটপুট 2। প্রথমে [2, 4, 4, 2] মুছে দিলে [6, 10, 6] থাকে, যা প্যালিনড্রোম — আবার মুছে দিলে লিস্ট খালি হয়।

সমাধানের পদ্ধতি

ডাইনামিক প্রোগ্রামিং (ইন্টারভ্যাল DP) + মেমোইজেশন

1. dp[i][j] = সাবঅ্যারে nums[i...j] খালি করার ন্যূনতম অপারেশন।
2. বেস কেস:
   • i > j: ০
   • i == j: ১
   • j - i == 1: nums[i] == nums[j] ? 1 : 2
3. ট্রানজিশন:
   • যদি nums[i] == nums[i+1]: 1 + dfs(i+2, j)
   • 1 + min(dfs(i+1, j), dfs(i, j-1))
   • যদি nums[i] == nums[j]: dfs(i+1, j-1)
   • সব k এর জন্য যেখানে nums[i] == nums[k]: dfs(i+1, k-1) + dfs(k+1, j)
4. মেমোইজেশন ব্যবহার করে পুনরাবৃত্তি এড়িয়ান।

উদাহরণ কোড

#include <bits/stdc++.h>
using namespace std;

int dp[105][105];

int dfs(int i, int j, vector<int>& v) {
    int ret = INT_MAX;
    if (i > j) return 0;
    if (i == j) return 1;
    if (j - i == 1) return v[i] == v[j] ? 1 : 2;
    if (i + 1 <= j && v[i] == v[i + 1])
        ret = 1 + dfs(i + 2, j, v);
    if (dp[i][j] != -1) return dp[i][j];
    ret = min({ret, 1 + min(dfs(i + 1, j, v), dfs(i, j - 1, v))});
    if (v[i] == v[j])
        ret = min(ret, dfs(i + 1, j - 1, v));
    for (int k = i + 2; k < j; k++) {
        if (v[i] == v[k])
            ret = min(ret, dfs(i + 1, k - 1, v) + dfs(k + 1, j, v));
    }
    return dp[i][j] = ret;
}

int solve(vector<int>& nums) {
    memset(dp, -1, sizeof dp);
    int n = nums.size();
    return dfs(0, n - 1, nums);
}

int main() {
    vector<int> v = {6, 2, 4, 4, 2, 10, 6};
    cout << solve(v);
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: {6, 2, 4, 4, 2, 10, 6}

আউটপুট: 2