Chương trình tìm số phép toán tối thiểu để hai danh sách tăng chặt trong Python

Mô tả bài toán

Cho hai danh sách A và B cùng độ dài. Mỗi phép toán cho phép hoán vị A[i] và B[i]. Tìm số phép toán tối thiểu để cả hai danh sách đều tăng chặt.

Ví dụ: A = [2, 8, 7, 10], B = [2, 4, 9, 10] → đầu ra 1 (hoán vị 7 và 9).

Giải thuật (Đệ quy có nhớ - DP)

1. Định nghĩa hàm dp(i, prev_swapped) trả về số phép toán tối thiểu từ chỉ số i đến cuối, biết ở bước trước có hoán vị hay không.
2. Cơ sở: nếu i == len(A) trả về 0.
3. Nếu i == 0: trả về min của dp(1, False) và 1 + dp(1, True).
4. Ngược lại:
   • Lấy giá trị trước prev_A = A[i-1], prev_B = B[i-1]. Nếu prev_swapped thì hoán vị chúng.
   • Nếu A[i] <= prev_A hoặc B[i] <= prev_B: bắt buộc hoán vị ở bước này → trả về 1 + dp(i+1, True).
   • Ngược lại: ans = dp(i+1, False). Nếu A[i] > prev_B và B[i] > prev_A thì có thể hoán vị → ans = min(ans, 1 + dp(i+1, True)). Trả về ans.
5. Gọi dp(0, False).

Ví dụ mã Python

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