सूचियों को सख्ती से बनाने के लिए आवश्यक संचालन की न्यूनतम संख्या खोजने के लिए कार्यक्रम अजगर में बढ़ रहा है

मान लीजिए कि हमारे पास ए और बी नामक संख्याओं की दो सूची है, और वे समान लंबाई के हैं। अब विचार करें कि हम एक ऑपरेशन कर सकते हैं जहां हम नंबर ए [i] और बी [i] स्वैप कर सकते हैं। हमें दोनों सूचियों को सख्ती से बढ़ाने के लिए आवश्यक संचालन की संख्या का पता लगाना होगा।

इसलिए, यदि इनपुट A =[2, 8, 7, 10] B =[2, 4, 9, 10] जैसा है, तो आउटपुट 1 होगा, क्योंकि हम A में 7 और B में 9 स्वैप कर सकते हैं। सूचियाँ ए =[2, 8, 9, 10] और बी =[2, 4, 7, 10] की तरह होंगी जो दोनों सख्ती से बढ़ती सूचियाँ हैं।

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

• एक फ़ंक्शन को परिभाषित करें dp() । यह मुझे ले जाएगा, prev_swapped
• यदि A का आकार i के समान है, तो
  • वापसी 0
• अन्यथा जब मैं 0 के समान हो, तो
  • न्यूनतम dp(i + 1, False) और 1 + dp(i + 1, True) लौटाएं
• अन्यथा,
  • prev_A :=A[i - 1]
  • prev_B :=B[i - 1]
  • अगर prev_swapped सही है, तो
    • prev_A और prev_B को स्वैप करें
  • अगर A[i] <=prev_A या B[i] <=prev_B, तो
    • रिटर्न 1 + डीपी(i + 1, ट्रू)
  • अन्यथा,
    • उत्तर:=डीपी(i + 1, गलत)
    • अगर A[i]> prev_B और B[i]> prev_A, तो
      • उत्तर:=न्यूनतम उत्तर, 1 + डीपी(i + 1, सत्य)
    • वापसी उत्तर
  • मुख्य विधि से फ़ंक्शन को कॉल करें dp(0, False) और परिणाम के रूप में उसका मान लौटाएं

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें:

उदाहरण कोड

class Solution:
   def solve(self, A, B):
      def dp(i=0, prev_swapped=False):
         if len(A) == i:
            return 0
         elif i == 0:
            return min(dp(i + 1), 1 + dp(i + 1, True))
         else:
            prev_A = A[i - 1]
            prev_B = B[i - 1]
            if prev_swapped:
               prev_A, prev_B = prev_B, prev_A
            if A[i] <= prev_A or B[i] <= prev_B:
               return 1 + dp(i + 1, True)
            else:
               ans = dp(i + 1)
            if A[i] > prev_B and B[i] > prev_A:
               ans = min(ans, 1 + dp(i + 1, True))
            return ans

         return dp()

ob = Solution()
A = [2, 8, 7, 10]
B = [2, 4, 9, 10]
print(ob.solve(A, B))

इनपुट

[2, 8, 7, 10], [2, 4, 9, 10]

आउटपुट

1