题目描述

给你数字 k，请你返回和为 k 的斐波那契数字的 最少数目，其中，每个斐波那契数字都可以被使用多次。

斐波那契数字定义为：

• F1 = 1
• F2 = 1
• Fn = Fn-1 + Fn-2， 其中 n > 2。

数据保证对于给定的 k，一定能找到可行解。

样例

输入：k = 7
输出：2 
解释：斐波那契数字为：1，1，2，3，5，8，13，...
对于 k = 7 ，我们可以得到 2 + 5 = 7 。

输入：k = 10
输出：2 
解释：对于 k = 10，我们可以得到 2 + 8 = 10。

输入：k = 19
输出：3 
解释：对于 k = 19，我们可以得到 1 + 5 + 13 = 19。

限制

• 1 <= k <= 10^9

算法

(贪心) $O(\log k)$

1. 我们从尽可能大的斐波那契数字开始往下来凑 k。
2. 下面简单证明正确性：
   • 对于一个最优解，如果存在两个相邻的斐波那契数，或者有重复的斐波那契数，则可以通过不断迭代，变为另一个最优解，满足不存在相邻的或重复的斐波那契数。
   • 这是因为 $f_i + f_{i+1} = f_{i+2}$，以及 $f_{i+1} = f_i + f_{i-1}$ 和 $f_i = f_{i-1} + f_{i-2}$，所以 $2f_i = f_{i+1} + f_{i-2}$。对于数字 1 来说，重复的 1 总可以换到更大的数字上，最终最优解中 1 的个数最多为一个。
   • 基于以上两个限制，我们发现，$f_1 + f_3 + \dots + f_{2n-1} = f_{2n}$ 且 $f_2 + f_4 + \dots + f_{2n} = f_{2n+1} - 1$，所以我们需要从尽可能大的数字开始取。

时间复杂度

• 小于 k 的斐波那契数个数量级是 $O(\log k)$ 的，所以时间复杂度也是 $O(\log k)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

class Solution {
public:
    int findMinFibonacciNumbers(int k) {
        int x = 1, y = 1;
        while (x + y <= k) {
            int t = x + y;
            x = y; y = t;
        }

        int ans = 0;
        while (k > 0) {
            if (k >= y) {
                k -= y;
                ans++;
            }
            int t = y - x;
            y = x; x = t;
        }

        return ans;
    }
};