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

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

ตัวอย่าง: A = [2, 8, 7, 10], B = [2, 4, 9, 10] ผลลัพธ์คือ 1 สลับ 7 กับ 9 ได้ A = [2, 8, 9, 10], B = [2, 4, 7, 10]

ขั้นตอนการแก้ปัญหา

1. สร้างฟังก์ชัน DP dp(i, prev_swapped):
   • ถ้า i == len(A) คืน 0
   • ถ้า i == 0 คืน min(dp(1, False), 1 + dp(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
2. คืนค่า 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