কঠোরভাবে তালিকা তৈরি করার জন্য প্রয়োজনীয় ন্যূনতম সংখ্যক অপারেশন খুঁজে বের করার জন্য প্রোগ্রাম পাইথনে বৃদ্ধি

ধরুন আমাদের কাছে A এবং B নামক দুটি সংখ্যার তালিকা আছে এবং সেগুলো একই দৈর্ঘ্যের। এখন বিবেচনা করুন আমরা একটি অপারেশন করতে পারি যেখানে আমরা A[i] এবং B[i] নম্বরগুলি অদলবদল করতে পারি। উভয় তালিকা কঠোরভাবে বাড়ানোর জন্য আমাদের প্রয়োজনীয় অপারেশনের সংখ্যা খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুটটি A =[2, 8, 7, 10] B =[2, 4, 9, 10] এর মত হয়, তাহলে আউটপুট হবে 1, যেমন আমরা A-তে 7 এবং B-তে 9টি অদলবদল করতে পারি। তালিকাগুলি A =[2, 8, 9, 10] এবং B =[2, 4, 7, 10] এর মতো হবে যা উভয়ই কঠোরভাবে ক্রমবর্ধমান তালিকা।

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

• একটি ফাংশন dp() সংজ্ঞায়িত করুন। এটি i, 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 + dp(i + 1, True)
  • অন্যথায়,
    • উত্তর :=dp(i + 1, False)
    • যদি A[i]> prev_B এবং B[i]> prev_A, তাহলে
      • উত্তর :=সর্বনিম্ন উত্তর, 1 + dp(i + 1, True)
    • উত্তর ফেরত দিন
  • প্রধান পদ্ধতি থেকে ফাংশনটি 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