Find the Minimum Number of Fibonacci Numbers Whose Sum Is K

Problem Statement:

Given an integer k, return the minimum number of Fibonacci numbers whose sum is equal to k. The same Fibonacci number can be used multiple times.
The Fibonacci numbers are defined as:
F1 = 1
F2 = 1
Fn = Fn-1 + Fn-2 for n > 2.
It is guaranteed that for the given constraints we can always find such Fibonacci numbers that sum up to k.
 
Example 1:
Input: k = 7
Output: 2 
Explanation: The Fibonacci numbers are: 1, 1, 2, 3, 5, 8, 13, ... 
For k = 7 we can use 2 + 5 = 7.

Example 2:
Input: k = 10
Output: 2 
Explanation: For k = 10 we can use 2 + 8 = 10.

Example 3:
Input: k = 19
Output: 3 
Explanation: For k = 19 we can use 1 + 5 + 13 = 19.



Solution:
class Solution:
    def findMinFibonacciNumbers(self, k: int) -> int:
        
        ##### O(N);O(N)
        #####  N be the length of fib sequence where last number in the sequence is less than or equal to k
             
        if k==1:
            return 1
        
        # initialize the fib sequence
        fib=[1,1]
        
        # temp will hold second last number from fib
        temp=fib[-2]
        
        # loop until the last number in fib is less than equal to k
        while fib[-1]<=k:
            
            # append next fib number and update temp
            fib.append(fib[-1]+temp)
            temp=fib[-2]
    
        # as one extra number is appended in the sequence, pop it
        fib.pop()
        
        # set curr number to k and initialize count
        curr=k
        cnt=0
        
        # traverse from right to left on the fib sequence
        for each in range(len(fib)-1,-1,-1):
            
            # if curr is zero, we got the count of elements which sums to k
            if curr==0:
                return cnt
            
            # if the current number from fib sequence is less than curr, pick that number and update curr and increment count
            if fib[each]<=curr:
                cnt+=1
                curr-=fib[each]
        return cnt