<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
{
public:
    int findMinFibonacciNumbers(int k)
    {
        const std::vector<int> fibonacci = {
            1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 
            1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 
            121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 
            3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 
            63245986, 102334155, 165580141, 267914296, 433494437, 701408733
        };

        int count = 0;
        int index = fibonacci.size() - 1;

        while (k > 0)
        {
            // Use the largest Fibonacci number less than or equal to k
            if (fibonacci[index] <= k)
            {
                k -= fibonacci[index];
                ++count;
            }
            // Move to the next smaller Fibonacci number
            --index;
        }

        return count;
    }
};
8100