सी ++ में ऐरे को सख्ती से बढ़ाना

मान लीजिए कि हमारे पास दो सरणियाँ हैं arr1 और arr2, ये पूर्णांक संख्याओं को संग्रहीत कर सकते हैं। हमें arr1 को सख्ती से बढ़ाने के लिए आवश्यक न्यूनतम संख्या में संचालन का पता लगाना होगा। यहां, हम दो सूचकांक 0 <=i

अगर हम caPending-3n एरे arr1 को सख्ती से नहीं बढ़ाते हैं, तो -1 लौटाएं।

इसलिए, यदि इनपुट arr1 =[1,5,3,7,8], arr2 =[1,3,2,5] जैसा है, तो आउटपुट 1 होगा, क्योंकि हम 5 को 2 से बदल सकते हैं, फिर सरणी [1,2,3,7,8] होगी।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक फ़ंक्शन हल करें () को परिभाषित करें, यह एक सरणी arr1, एक सरणी arr2, i, j, prev, एक 2D सरणी dp,

  लेगा

• अगर i>=arr1 का आकार, तो −

  • वापसी 1

• j =arr2 के उप-सरणी का पहला तत्व arr2[j] और ऊपरी

  . से

• अगर dp[i, j] -1 के बराबर नहीं है, तो -

  • वापसी डीपी [i, जे]

• ret :=arr2 + 1 का आकार

• अगर पिछला

  • रिट:=न्यूनतम रिट और हल (arr1, arr2, i + 1, j, arr1[i], dp)

• अगर j

  • रिट:=न्यूनतम रिट और 1 + हल (arr1, arr2, i + 1, j, arr2[j], dp)

• वापसी डीपी [i, जे] =सेवानिवृत्त

• मुख्य विधि से, निम्न कार्य करें -

• सरणी को क्रमबद्ध करें arr2

• n :=arr1 का आकार

• मी :=arr2 का आकार

• 2005 x 2005 के आकार के एक 2डी सरणी डीपी को परिभाषित करें और इसे -1 से भरें

• रिट:=हल करें (arr1, arr2, 0, 0, -inf, dp)

• वापसी (यदि रिट> एआर 2 का आकार, फिर -1, अन्यथा सेवानिवृत्त -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