পাইথনে দুটি লিস্টকে স্ট্রিক্টলি ইনক্রিজিং করার জন্য ন্যূনতম সওয়াপের সংখ্যা বের করার প্রোগ্রাম

মান লক্ষ্য করুন আমাদের কাছে সমান দৈর্ঘ্যের দুটি সংখ্যার তালিকা A এবং B আছে। এখন একটি অপারেশন বিবেচনা করুন যেখানে আমরা A[i] এবং B[i] কে সওয়াপ করতে পারি। আমাদের কাজ হল উভয় তালিকাকেই স্ট্রিক্টলি ইনক্রিজিং बनाने জন্য প্রয়োজনীয় অপারেশনের সংখ্যা বের করা।

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

• একটি dp() ফাংশন ডিফাইন করুন যা i, prev_swapped নেবে।
  • যদি len(A) == i হয়, তবে 0 রিটার্ন করুন।
  • অন্যথায় যদি i == 0 হয়, তবে min(dp(i+1, False), 1 + dp(i+1, True)) রিটার্ন করুন।
  • অন্যথায়:
    • prev_A := A[i-1], prev_B := B[i-1]
    • যদি prev_swapped_true হয়, তবে prev_A এবং prev_B সওয়াপ করুন।
    • যদি A[i] <= prev_A বা B[i] <= prev_B হয়, তবে 1 + dp(i+1, True) রিটার্ন করুন।
    • অন্যথায়:
      • ans := dp(i+1, False)
      • যদি A[i] > prev_B এবং B[i] > prev_A হয়, তবে ans := min(ans, 1 + dp(i+1, True))
      • ans রিটার্ন করুন।
• মূল মেথড থেকে 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