C++ এ অদ্ভুত প্রিন্টার

ধরুন একটি অদ্ভুত প্রিন্টার আছে এটির কিছু প্রয়োজনীয়তা রয়েছে −

• প্রিন্টার প্রতিবার একই অক্ষরের শুধুমাত্র একটি ক্রম প্রিন্ট করতে পারে।
• প্রতিটি পালা করে, প্রিন্টার নতুন অক্ষর মুদ্রণ করতে পারে যেকোন স্থান থেকে শুরু করে শেষ করে, এবং মূল বিদ্যমান অক্ষরগুলিকে কভার করবে।

তাই যদি আমাদের একটি স্ট্রিং থাকে যা নিম্ন অক্ষর নিয়ে গঠিত, আমাদের কাজ হল প্রিন্টারটি প্রিন্ট করার জন্য প্রয়োজনীয় ন্যূনতম সংখ্যা গণনা করা।

সুতরাং যদি ইনপুটটি "aaabba" এর মত হয়, তাহলে এটি 2টি বাঁক নেবে, প্রথমে aaaaa তারপর b' অক্ষরগুলি প্রতিস্থাপন করে।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• n :=s এর আকার
• যদি n 0 এর মত হয়, তাহলে:0 ফেরত দিন
• অর্ডার n x n এর একটি 2D অ্যারে dp সংজ্ঞায়িত করুন, এটিকে অসীম দিয়ে পূরণ করুন
• আরম্ভ করার জন্য l :=1, যখন l <=n, আপডেট করুন (l 1 দ্বারা বাড়ান), −
  করুন
  • আরম্ভ করার জন্য i :=0, j :=l - 1, যখন j করুন
  • যদি l 1 এর মত হয়, তাহলে:dp[i, j] :=1
• অন্যথায় যখন l 2 এর সমান হয়, তখন −
  • dp[i, j] :=1 যখন s[i] s[j] এর মত হয় অন্যথায় 2
• অন্যথায়
  • আরম্ভ করার জন্য k :=i, যখন k করুন
  • temp :=dp[i, k] + dp[k + 1, j]
  • dp[i, j] :=সর্বনিম্ন dp[i, j] এবং (temp – 1 যখন s[k] s[j] এর মতই হয় অন্যথায় temp।

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
class Solution {
public:
   int strangePrinter(string s) {
      int n = s.size();
      if(n == 0) return 0;
      vector < vector <int> > dp(n, vector <int>(n, INF));
      for(int l = 1; l <= n; l++){
      for(int i = 0, j = l - 1; j < n; i++, j++){
         if(l == 1){
            dp[i][j] = 1;
            }else if(l == 2){
               dp[i][j] = s[i] == s[j] ? 1 : 2;
            }else{
               for(int k = i; k < j; k++){
                  int temp = dp[i][k] + dp[k + 1][j];
                  dp[i][j] = min(dp[i][j], s[k] == s[j] ? temp - 1: temp);
               }
            }
         }
      }
      return dp[0][n - 1];
   }
};
main(){
   Solution ob;
   cout << (ob.strangePrinter("aaabba"));
}

ইনপুট

“2*”

আউটপুট

2