โปรแกรมค้นหาจำนวนขั้นต่ำของการดำเนินการที่จำเป็นในการสร้างรายการอย่างเคร่งครัด เพิ่มขึ้นใน python

สมมติว่าเรามีรายการตัวเลขสองรายการที่เรียกว่า A และ B และมีความยาวเท่ากัน ตอนนี้ให้พิจารณาว่าเราสามารถดำเนินการที่เราสามารถสลับตัวเลข A[i] และ B[i] ได้ เราต้องหาจำนวนการดำเนินการที่จำเป็นเพื่อให้ทั้งสองรายการเพิ่มขึ้นอย่างเคร่งครัด

ดังนั้น หากอินพุตเป็น A =[2, 8, 7, 10] B =[2, 4, 9, 10] ผลลัพธ์จะเป็น 1 เนื่องจากเราสามารถสลับ 7 ใน A และ 9 ใน B ได้ รายการจะเป็นแบบ 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, จริง)
  • มิฉะนั้น
    • ตอบ :=dp(i + 1, เท็จ)
    • ถ้า A[i]> prev_B และ B[i]> prev_A แล้ว
      • ans :=ขั้นต่ำของ ans, 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