Problem statement

https://binarysearch.com/problems/Fibonacci-Subset-Sum/

Solution

Equal to Leetcode 1414. Find the Minimum Number of Fibonacci Numbers Whose Sum Is K

Complexity

It is O(log n) for time and space.

Code

class Solution:
    def solve(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