Kiểm tra số có thể biểu diễn thành tổng A và B không (Python)

Bài toán: Cho target, A, B. Kiểm tra có thể cộng A và B nhiều lần (thứ tự bất kỳ) để được target không.

Đệ quy + Memoization (DP)

Từ 0, mỗi bước có thể +A hoặc +B. Dùng mảng is_ok đánh dấu các giá trị đã đạt được để tránh lặp.

Triển khai Python

def util(x, a, b, is_ok, target):
    if x > target:
        return
    if is_ok[x]:
        return
    is_ok[x] = True
    util(x + a, a, b, is_ok, target)
    util(x + b, a, b, is_ok, target)

def solve(target, a, b):
    is_ok = [False] * (target + 1)
    util(0, a, b, is_ok, target)
    return is_ok[target]

# Test
print(solve(26, 5, 7))   # True: 7+7+7+5 = 26
print(solve(10, 3, 6))   # False: không thể tạo 10 từ 3,6
print(solve(100, 7, 13)) # True

Kết quả

True

Giải thích

• Đây là bài toán Coin Change / Unbounded Knapsack biến thể chỉ cần kiểm tra khả thi (không cần tối ưu).
• is_ok[x] = True nghĩa là có thể tạo ra tổng x.
• Đệ quy từ 0, lan truyền +A, +B. Memoization tránh tính lại.
• Độ phức tạp: O(target) thời gian và không gian.
• Có thể thay bằng DP bottom-up hoặc kiểm tra GCD (nếu gcd(A,B) chia hết target thì True cho target đủ lớn - Chicken McNugget theorem).