Minimum Fibonacci Terms Summing to K

Minimum Fibonacci Terms Summing to K asks for the fewest Fibonacci numbers (repeats allowed) that add up to k. It is a classic greedy problem: a surprisingly simple "always grab the biggest" rule turns out to be provably optimal.

The slow way first

You could treat this like making change: try every combination of Fibonacci numbers that sums to k and keep the smallest count. That is an exponential search, or an O(n·k) dynamic-programming table at best. For large k it is wasteful.

The question to ask: do I really need to explore choices, or is one obvious move always right? Here, taking the largest Fibonacci number that fits is never a mistake.

The idea: take the biggest that fits

Generate every Fibonacci number <= k. Then repeatedly subtract the largest one that is still <= remaining, counting each subtraction. Because consecutive Fibonacci numbers satisfy fib[i] + fib[i-1] = fib[i+1], you can prove the greedy choice always leads to the minimum count (this is Zeckendorf's theorem in disguise).

The key insight: never use a number larger than what remains, and always prefer the largest legal one. You walk the Fibonacci list from the top down and never need to revisit a choice.

Walk through it

Step through the animation. The candidate Fibonacci numbers sit in cells. The pick pointer drops onto the largest one that fits each round. For k = 19: take 13 (remaining 6), then 5 (remaining 1), then 1 (remaining 0). Three terms, done.

Pseudocode

build fibs = [1, 1, 2, 3, 5, ...] up to k
count = 0
i = index of the largest fib
while k > 0:
    if fibs[i] <= k:
        k -= fibs[i]          # use this fib
        count += 1
    else:
        i -= 1                # too big, try a smaller fib
return count

The Python solution

def min_fib_terms(k):
    fibs = [1, 1]
    while fibs[-1] + fibs[-2] <= k:
        fibs.append(fibs[-1] + fibs[-2])
    count = 0
    i = len(fibs) - 1
    while k > 0:
        if fibs[i] <= k:
            k -= fibs[i]
            count += 1
        else:
            i -= 1
    return count

• We first build fibs until the next Fibonacci number would exceed k.
• i starts at the last (largest) Fibonacci number.
• Line 8 checks whether the current candidate fits in what remains.
• Lines 9 and 10 are the greedy take: subtract it and bump the count.
• If it does not fit, we step i down to a smaller Fibonacci number and try again.
• We never move i back up, so the loop runs in linear time over the list.

Complexity

There are only about log_φ(k) Fibonacci numbers <= k (they grow exponentially), so both building the list and scanning it take O(log k) time and space. The greedy rule replaces a whole DP table with one downward pass.

When this pattern shows up

Practice