สมมติว่าเรามีตัวเลข n พิจารณาว่ามีส้ม n ลูกในครัว และเรากินส้มบางส่วนทุกวันโดยปฏิบัติกฎเหล่านี้: 1. กินส้ม 1 ลูก 2. ถ้า n เป็นเลขคู่ กิน n/2 ลูก 3. ถ้า n หาร 3 ลงตัว กิน 2*(n/3) ลูก เราสามารถเลือกได้เพียงหนึ่งตัวเลือกต่อวัน เราต้องหาจำนวนวันน้อยที่สุดที่จะกินส้ม n ลูกหมด
เช่น ถ้าอินพุตคือ n = 10 ผลลัพธ์จะเป็น 4 เพราะ:
- วันที่ 1 กิน 1 ลูก 10 - 1 = 9
- วันที่ 2 กิน 6 ลูก 9 - 2*(9/3) = 9 - 6 = 3
- วันที่ 3 กิน 2 ลูก 3 - 2*(3/3) = 3 - 2 = 1
- วันที่ 4 กินลูกสุดท้าย 1 - 1 = 0
วิธีแก้ปัญหา
- กำหนดฟังก์ชัน fun() รับ n:
- ถ้า n อยู่ใน memo: return memo[n]
- ถ้า n <= 2: return n
- memo[n] := 1 + min(n%2 + fun(n//2), n%3 + fun(n//3))
- return memo[n]
- จากเมธอดหลัก:
- memo := แมปใหม่
- return fun(n)
ตัวอย่าง
def solve(n):
def fun(n):
if n in memo:
return memo[n]
if n <= 2:
return n
memo[n] = 1 + min(n%2 + fun(n//2), n%3 + fun(n//3))
return memo[n]
memo = {}
return fun(n)
n = 12
print(solve(n))
อินพุต
7, [5,1,4,3]
เอาต์พุต
4
