Problem statement

https://leetcode.com/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k/

Solution

The idea is to start greedily with the biggest numbers.

Complexity

It is O(x), where x is the answer for our problem, can be estimated as O(log k).

Code

class Solution:
    def findMinFibonacciNumbers(self, k):
        dp = [1, 1]
        while dp[-1] < k:
            dp += [dp[-1] + dp[-2]]
            
        ans = 0
        i = len(dp) - 1
        for x in range(i, -1, -1):
            if dp[x] <= k:
                ans += 1
                k -= dp[x]

        return ans