C++-এ অ্যারেকে কঠোরভাবে বৃদ্ধি করুন

ধরুন আমাদের দুটি অ্যারে রয়েছে arr1 এবং arr2, এগুলি পূর্ণসংখ্যা সংরক্ষণ করতে পারে। আমাদের arr1 কঠোরভাবে বাড়ানোর জন্য প্রয়োজনীয় ন্যূনতম সংখ্যক অপারেশন খুঁজে বের করতে হবে। এখানে, আমরা দুটি সূচক 0 <=i

যদি আমরা caPending-3 অ্যারেকে কঠোরভাবে বৃদ্ধি না করি, তাহলে -1 রিটার্ন করি।

সুতরাং, যদি ইনপুটটি arr1 =[1,5,3,7,8], arr2 =[1,3,2,5] এর মত হয়, তাহলে আউটপুট হবে 1, যেমন আমরা 5 কে 2 দিয়ে প্রতিস্থাপন করতে পারি, তাহলে অ্যারে হবে [1,2,3,7,8]।

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

• একটি ফাংশন সল্ভ() নির্ধারণ করুন, এটি একটি অ্যারে অ্যারে 1, অ্যারে অ্যারে 2, i, j, পূর্ববর্তী, একটি 2D অ্যারে dp,

• যদি i>=arr1 এর আকার হয়, তাহলে −

  • রিটার্ন 1

• j =arr2 [j] এবং উপরের থেকে arr2 এর সাবয়ারের প্রথম উপাদান

• যদি dp[i, j] -1 এর সমান না হয়, তাহলে −

  • dp[i, j]

    ফেরত দিন

• ret :=arr2 + 1

  এর আকার

• যদি পূর্ববর্তী

  • ret :=ret এবং সমাধানের সর্বনিম্ন (arr1, arr2, i + 1, j, arr1[i], dp)

• যদি j

  • ret :=ret এর সর্বনিম্ন এবং 1 + সমাধান (arr1, arr2, i + 1, j, arr2[j], dp)

• রিটার্ন dp[i, j] =ret

• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -

• অ্যারে সাজান arr2

• n :=arr1 এর আকার

• m :=arr2 এর আকার

• 2005 x 2005 আকারের একটি 2D অ্যারে ডিপি সংজ্ঞায়িত করুন এবং এটি -1 দিয়ে পূরণ করুন

• ret :=সমাধান (arr1, arr2, 0, 0, -inf, dp)

• রিটার্ন (যদি ret> arr2 এর আকার, তারপর -1, অন্যথায় ret - 1)

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

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(vector<int>& arr1, vector<int>& arr2, int i, int j, int prev, vector<vector<int> >& dp){
      if (i >= arr1.size())
         return 1;
      j = upper_bound(arr2.begin() + j, arr2.end(), prev) - arr2.begin();
      if (dp[i][j] != -1)
         return dp[i][j];
      int ret = arr2.size() + 1;
      if (prev < arr1[i]) {
         ret = min(ret, solve(arr1, arr2, i + 1, j, arr1[i], dp));
      }
      if (j < arr2.size()) {
         ret = min(ret, 1 + solve(arr1, arr2, i + 1, j, arr2[j], dp));
      }
      return dp[i][j] = ret;
   }
   int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2){
      sort(arr2.begin(), arr2.end());
      int n = arr1.size();
      int m = arr2.size();
      vector<vector<int> > dp(2005, vector<int>(2005, -1));
      int ret = solve(arr1, arr2, 0, 0, INT_MIN, dp);
      return ret > arr2.size() ? -1 : ret - 1;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,5,3,7,8}, v1 = {1,3,2,5};
   cout << (ob.makeArrayIncreasing(v,v1));
}

ইনপুট

{1,5,3,7,8}, {1,3,2,5}

আউটপুট

1