पायथन में दो सूचियों को सख्ती से बढ़ता हुआ बनाने के लिए न्यूनतम ऑपरेशन्स खोजने का प्रोग्राम

मान लीजिए हमारे पास 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 लेता है
यदि 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 सच है, तो 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]