Chương trình tìm số lượng thao tác tối thiểu cần thiết để tạo danh sách một cách nghiêm ngặt Tăng lên trong python

Giả sử chúng ta có hai danh sách các số được gọi là A và B, và chúng có cùng độ dài. Bây giờ hãy xem xét chúng ta có thể thực hiện một phép toán trong đó chúng ta có thể hoán đổi số A [i] và B [i]. Chúng tôi phải tìm số lượng các hoạt động cần thiết để làm cho cả hai danh sách tăng lên một cách nghiêm ngặt.

Vì vậy, nếu đầu vào là A =[2, 8, 7, 10] B =[2, 4, 9, 10], thì đầu ra sẽ là 1, vì chúng ta có thể hoán đổi 7 trong A và 9 trong B. Sau đó danh sách sẽ giống như A =[2, 8, 9, 10] và B =[2, 4, 7, 10] đều là danh sách tăng dần.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:

• Định nghĩa một hàm dp (). Điều này sẽ đưa tôi, trước khi được thay đổi
• nếu kích thước của A giống với i, thì
  • trả về 0
• ngược lại, khi tôi giống 0, thì
  • trả về tối thiểu dp (i + 1, False) và 1 + dp (i + 1, True)
• nếu không,
  • prev_A:=A [i - 1]
  • before_B:=B [i - 1]
  • nếu pre_swapped là True, thì
    • hoán đổi trước trước_A và trước_ sau_B
  • nếu A [i] <=trước_A hoặc B [i] <=trước_B, thì
    • trả về 1 + dp (i + 1, True)
  • nếu không,
    • ans:=dp (i + 1, Sai)
    • nếu A [i]> prev_B và B [i]> prev_A, thì
      • ans:=tối thiểu ans, 1 + dp (i + 1, True)
    • trả lại ans
  • Từ phương thức main, hãy gọi hàm dp (0, False) và trả về giá trị của nó là kết quả

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:

Mã mẫu

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))

Đầu vào

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

Đầu ra

1