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

斐波那契数字定义为：

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

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

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

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

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

提示：

• 1 <= k <= 10^9

分析：

方法1：贪心+递归

其实这道题很容易看出 k 的组成数字都有离它最近的斐波那契数字，只要每次找到离它最近的斐波那契数字，然后 k 减去最近的斐波那契数字，再继续找新 k 的最近斐波那契数字，直到 k 为 0，那么找的次数就为最少数目，用一个递归可以轻松解决。但是这些思路都是建立在 k 的组成数字一定有离它最近的数 的基础上，接下来我们来证明这个条件是正确的：

令离 k 最近的数为 Fn，易证 k 的组成一定不含连续数字，因为连续数字加起来就是一个新的斐波那契数字，所以假设 k 的组成不含 Fn，那么 k 的最大值 max 满足：

1. 令 max  = F(n - 1) + F(n - 3) + ... + F1 （n 为 偶数）或 max = F(n - 1) + F(n - 3) + ... + F2（n 为 奇数）
2. 因为 Fn = F(n - 1) + F(n - 2) = F(n - 1) + F(n - 3) + F(n - 4) = F(n - 1) + F(n - 3) + F(n - 5) + ... + F1 + F1（n 为 偶数）或  F(n - 1) + F(n - 3) + F(n - 5) + ... + F2 + F1（n 为 奇数）
3. 所以Fn >= max
4. 因为 k >= Fn
5. 所以在 F(n - ?) 不重复的情况下，一定有 Fn。

下面考虑重复的情况：

1. 令 max = F(n - 1) + F(n - 1)
2. 因为 F(n - 1) = F(n - 2) + F(n - 3)
3. 所以 max = F(n - 1) + F(n - 2) + F(n - 3) = Fn + F(n - 3)
4. 所以在重复的情况下，重复的运算式也可以转换为含 Fn 运算式

因此，无论什么情况，k 的组成数字一定有离它最近的斐波那契数字。

时间复杂度：O(log n) 
空间复杂度：O(log n)

class Solution {
    public int findMinFibonacciNumbers(int k) {
        //如果 k 为 0，返回 0
        if(k == 0){
            return 0;
        }
        //定义当前值，上一值，辅助变量
        int cur = 1, pre = 1, temp = 2;
        //给数组赋值
        while(cur <= k){
            //计算新的值
            temp = cur + pre;
            //上一值变为当前值
            pre = cur;
            //当前值变为新的值
            cur = temp;
        }
        //k 减去上一值，继续递归遍历
        return findMinFibonacciNumbers(k - pre) + 1;
    }
}

方法2：贪心+迭代

因为 方法1 每次递归都要重复创建斐波那契数列，比较浪费时间，为避免这种情况，我们可以用迭代的方式。因为找斐波那契数列的时候我们定义了记录上一值的变量，那么我们可以反编译斐波那契数列，如果 k 的值大于当前数字，就减去当前数字，继续遍历，直到 k 为 0，然后返回减去的次数即可。

时间复杂度：O(log n) 
空间复杂度：O(log n)

class Solution {
    public int findMinFibonacciNumbers(int k) {
        //定义当前值，上一值，辅助变量
        int cur = 1, pre = 1, temp = 2;
        //给数组赋值
        while(cur <= k){
            //计算新的值
            temp = cur + pre;
            //上一值变为当前值
            pre = cur;
            //当前值变为新的值
            cur = temp;
        }
        //记录数目
        int count = 0;
        //反编译斐波那契数列
        while(k > 0){
            //当前数字小于等于 k，k 减去当前数字
            if(cur <= k){
               k -= cur;
               count++;
            }
            //计算上上一值
            temp = cur - pre;
            //当前值变为上一值
            cur = pre;
            //上一值变为上上一值
            pre = temp;
        }
        //返回计数结果
        return count;
    }
}

题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k