Solution

Method 1 – Greedy (Zeckendorf's Theorem)

Intuition

To represent a number as the sum of the minimum number of Fibonacci numbers, always subtract the largest Fibonacci number less than or equal to the current value. This is based on Zeckendorf's theorem, which states every positive integer can be uniquely represented as the sum of non-consecutive Fibonacci numbers.

Approach

Generate all Fibonacci numbers up to k.
Start from the largest Fibonacci number and subtract it from k if it does not exceed k.
Repeat the process, counting each subtraction, until k becomes 0.
Return the count.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int findMinFibonacciNumbers(int k) {\n        vector<int> fib = {1, 1};\n        while(fib.back() < k) fib.push_back(fib[fib.size()-1] + fib[fib.size()-2]);\n        int ans = 0;\n        for(int i = fib.size()-1; i >= 0 && k > 0; --i) {\n            if(fib[i] <= k) {\n                k -= fib[i];\n                ++ans;\n            }\n        }\n        return ans;\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> findMinFibonacciNumbers</span><span style=\"color:#24292E;--shiki-dark:#E1E4

Related Tags