<p>Given an integer&nbsp;<code>k</code>, <em>return the minimum number of Fibonacci numbers whose sum is equal to </em><code>k</code>. The same Fibonacci number can be used multiple times.</p>

<p>The Fibonacci numbers are defined as:</p>

<ul>
	<li><code>F<sub>1</sub> = 1</code></li>
	<li><code>F<sub>2</sub> = 1</code></li>
	<li><code>F<sub>n</sub> = F<sub>n-1</sub> + F<sub>n-2</sub></code> for <code>n &gt; 2.</code></li>
</ul>
It is guaranteed that for the given constraints we can always find such Fibonacci numbers that sum up to <code>k</code>.
<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> k = 7
<strong>Output:</strong> 2 
<strong>Explanation:</strong> The Fibonacci numbers are: 1, 1, 2, 3, 5, 8, 13, ... 
For k = 7 we can use 2 + 5 = 7.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> k = 10
<strong>Output:</strong> 2 
<strong>Explanation:</strong> For k = 10 we can use 2 + 8 = 10.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> k = 19
<strong>Output:</strong> 3 
<strong>Explanation:</strong> For k = 19 we can use 1 + 5 + 13 = 19.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= 10<sup>9</sup></code></li>
</ul>

class Solution:
    def findMinFibonacciNumbers(self, k: int) -> int:


        fib = [0, 1]

        while fib[-1] <= k:
            fib.append(fib[-1] + fib[-2])
        
        ans = float('inf')

        i = len(fib) - 1 
        count = 0 
        while i >= 0 and k >= 0:
            if k == 0:
                return count  
            if fib[i] <= k:
                if k - fib[i] >= 0:
                    k = k - fib[i]
                    count += 1 
                else:
                    i -= 1 
            else:
                i -= 1 
            
        



        # dp = [k for _ in range(k + 1)]

        # dp[1] = 1 


        # for end in range(2, len(dp)):
        #     for start in range(0, end + 1):
        #         dp[end] = min(dp[end], dp[end - start] + 1)
        
        # print('dp', dp)
        # return dp[-1]


        # # def dfs(ind, target, path):
        #     nonlocal ans 
        #     if target == 0:
        #         if len(path) < ans:
        #             ans = len(path)
        #         return 
            
        #     if target < 0 or ind >= len(fib):
        #         return 
            
        #     for i in range(ind, len(fib)):
        #         dfs(i + 1, target - fib[i], path + [fib[i]])
        
        # dfs(0, k, [])
        # return ans 


















        # ans = float('inf')
        # if k == 1:
        #     return 1 

        # def dfs(prev, prev2, target, count):
        #     # print('prev', prev)
        #     # print('prev2', prev2)
        #     nonlocal ans 
        #     if target == 0:
        #         print('count', count)
        #         if count < ans:
        #             ans = count 
        #         return 
        #     if target < 0:
        #         return 

        #     dfs(prev + prev2, prev, target - prev - prev2, count + 1)

        # dfs(1, 0, k - 1, 2)
        # return ans if ans != math.inf else -1


        

        
16300