ตรวจสอบว่า N สามารถแทนเป็นผลรวมของ A และ B ที่เลือกจากเซต {A, B} ได้หรือไม่ด้วย Python

สมมติมี Target และตัวเลข A, B ต้องตรวจสอบว่าสามารถบวก A และ B ซ้ำๆ ได้เป็น Target หรือไม่

เช่น Input Target = 26, A = 5, B = 7 Output True เพราะ 7+7+7+5 = 26

ขั้นตอนแก้ (DFS + Memoization):

• ฟังก์ชัน util(x, a, b, is_ok, target): ถ้า x > target Return; ถ้า is_ok[x] Return; is_ok[x]=True; เรียก util(x+a) และ util(x+b)
• Main: สร้าง is_ok Array ขนาด target+1 เรียก util(0) Return is_ok[target]

ตัวอย่างโค้ด

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]

target = 26
A = 5
B = 7
print(solve(target, A, B))

Input

26, 5, 7

Output

True