Tìm số lượng số Fibonacci nhỏ nhất cộng thành n trong Python

Cho số n, tìm số lượng số Fibonacci ít nhất để tổng bằng n (mỗi số dùng nhiều lần).

Ví dụ: n = 20 → 3 (dùng 2, 5, 13).

Giải pháp: Tham lam (Zeckendorf's theorem). Sinh dãy Fibonacci ≤ n, lặp trừ số Fibonacci lớn nhất ≤ n còn lại.

Ví dụ triển khai

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

Đầu vào

20

Đầu ra

3