সি++-এ প্যালিনড্রোম পার্টিশনিং III (Palindrome Partitioning III)

মনে করুন, আমাদের কাছে একটি স্ট্রিং s আছে যাতে ছোট হাতের ইংরেজি অক্ষর রয়েছে এবং একটি পূর্ণসংখ্যা k। আমাদের কিছু শর্ত মানতে হবে:

• প্রথমে, s-এর কিছু ক্যারেক্টার (যদি প্রয়োজন হয়) পরিবর্তন করে অন্য ছোট হাতের ইংরেজি অক্ষরে রূপান্তর করতে হবে।
• তারপর স্ট্রিং s কে k টি সাবস্ট্রিংএ ভাগ করতে হবে যাতে প্রতিটি সাবস্ট্রিং প্যালিনড্রোম হয়।

আমাদের লক্ষ্য হলো স্ট্রিংটি ভাগ করার জন্য ন্যূনতম কতটি ক্যারেক্টার পরিবর্তন করতে হবে তা বের করা।

যেমন, স্ট্রিংটি "ababbc" এবং k = 2 হলে, উত্তর হবে ১। কারণ একটি ক্যারেক্টার পরিবর্তন করে এটি দুইটি প্যালিনড্রোম স্ট্রিংএ ভাগ করা সম্ভব। যদি 'c' কে 'b' বদলে দি, অথবা দ্বিতীয় শেষ 'b' কে 'c' বদলে দি, তবে আমরা "bbb" বা "cbc" নামে একটি প্যালিনড্রোম পাব, আরেকটি প্যালিনড্রোম হবে "aba"।

সমাধানের ধাপসমূহ

• 105 x 105 আকারের একটি memo অ্যারে সংজ্ঞায়িত করুন।
• solve() ফাংশন সংজ্ঞায়িত করুন, যা s, idx, k, এবং একটি ২D অ্যারে dp নিবে।
  • যদি idx == s.size() হয়, তবে (k == 0 ? 0 : 1000) রিটার্ন করুন।
  • যদি memo[idx][k] != -1 হয়, তবে memo[idx][k] রিটার্ন করুন।
  • যদি k <= 0 হয়, তবে INT_MAX রিটার্ন করুন।
  • ans := INT_MAX
  • i := idx থেকে s.size()-1 পর্যন্ত লুপ চালান
    • ans := min(ans, dp[idx][i] + solve(s, i+1, k-1, dp))
  • memo[idx][k] = ans রিটার্ন করুন।
• মূল ফাংশন থেকে:
  • n := s.size()
  • memo -1 দিয়ে ভরুন
  • n x n আকারের একটি ২D অ্যারে dp সংজ্ঞায়িত করুন
  • l := 2 থেকে n পর্যন্ত লুপ চালান
    • i := 0, j := l-1 থেকে শুরু করে j < n পর্যন্ত লুপ চালান
      • যদি l == 2 হয়, তবে dp[i][j] := (s[i] != s[j])
      • অন্যথায় dp[i][j] := dp[i+1][j-1] + (s[i] != s[j])
  • solve(s, 0, k, dp) রিটার্ন করুন

উদাহরণ

#include <bits/stdc++.h> using namespace std; typedef long long int lli; class Solution { public:    int memo[105][105];    lli solve(string s, int idx, int k, vector < vector <int> > &dp){       if(idx == s.size()) {          return k == 0? 0 : 1000;       }       if(memo[idx][k] != -1) return memo[idx][k];       if(k <= 0)return INT_MAX;       lli ans = INT_MAX;       for(int i = idx; i < s.size(); i++){          ans = min(ans, dp[idx][i] + solve(s, i + 1, k - 1, dp));       }       return memo[idx][k] = ans;    }    int palindromePartition(string s, int k) {       int n = s.size();       memset(memo, -1, sizeof(memo));       vector < vector <int> > dp(n, vector <int>(n));       for(int l =2; l <= n; l++){          for(int i = 0, j = l - 1; j <n; j++, i++){             if(l==2){                dp[i][j] = !(s[i] == s[j]);             }else{                dp[i][j] = dp[i+1][j-1] + !(s[i] == s[j]);             }          }       }       return solve(s, 0, k, dp);    } }; main(){    Solution ob;    cout << (ob.palindromePartition("ababbc", 2)); }

ইনপুট

"ababbc"

আউটপুট

1