หาจำนวนฟีโบนัชชีน้อยที่สุดที่รวมกันได้ n ใน Python

หาจำนวนน้อยที่สุดของเลขฟีโบนัชชีที่รวมกันได้ n (ใช้เลขซ้ำได้)

ตัวอย่าง: n = 20 → 3 (เพราะ 2 + 5 + 13 = 20)

แนวทาง (Greedy - Zeckendorf's Theorem)

1. สร้างลิสต์ฟีโบนัชชีจนเกิน n
2. วนลูป: ลบเลขฟีโบนัชชีตัวใหญ่ที่สุด ≤ n ออกจาก n นับจำนวนครั้ง
3. ทำซ้ำจน n = 0

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

class Solution:
    def solve(self, n):
        res = 0
        fibo = [1, 1]
        while fibo[-1] <= n:
            fibo.append(fibo[-1] + fibo[-2])
        
        while n:
            while fibo[-1] > n:
                fibo.pop()
            n -= fibo[-1]
            res += 1
        return res

ob = Solution()
n = 20
print(ob.solve(n))  # 3

อินพุต

20

เอาต์พุต

3