LEETCODE 1414. Find the Minimum Number of Fibonacci Numbers Whose Sum Is K 解题思路分析

题目大意：

和为 K 的最少斐波那契数字数目

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

斐波那契数字定义为：

• F₁ = 1
• F₂ = 1
• F_n = F_n-1 + F_n-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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1414

解题思路分析：

1. 先求出小于k的所有斐波那契数字，存放至List中。
2. 用k减去List中小于等于k的最大数字。
3. 重复第二步，直到k等于0为止，重复的次数即是返回结果。

这道题实际上使用到了贪心算法，即尽量使用大的数字去组合成k，这样才能保证使用的数字个数最少。使用贪心的基础是需要证明该贪心算法的正确性。我在网上看到了一个很好地证明，在这里引用过来仅供参考。

---

• 方案中不会包含相邻的数，因为相邻的两个数可以由它们的和代替，从而构造出数目更少的方案。
• 也不必要包含相同的数，因为f(n)+f(n)=f(n+1)+f(n-2) (n>=2)当n<2时，有f(2)=2f(1)=2f(0)；如此可以将方案中所有相同的数都替换掉。
• 选取小于f(n)的不相邻且不重复的数，其最大和为f(n-1)+f(n-3)+f(n-5)…+1<=f(n)。（n为奇数时直接可以f(0)+f(2)=f(3), f(3)+f(4)=f(5), … ,f(n-2)+f(n-1)=f(n); n为偶数时两边同时加上f(0)开始合并）。因此和为k的最小子数组中一定可以包含刚好不大于k的斐波那契数。例：4=1+3=2+2

实现代码：

public int findMinFibonacciNumbers(int k) {
    List<Integer> nums=new ArrayList<>();
    nums.add(1);
    int n1=1, n2=1;
    while(n1+n2<=k){
        int sum=n1+n2;
        n1=n2;
        n2=sum;
        nums.add(sum);
    }
    int res=0;
    while(k>0){
        for(int i=nums.size()-1;i>=0;i--){
            if(nums.get(i)<=k){
                k-=nums.get(i);
                res++;
                break;
            }
        }
    }
    return res;
}

本题解法执行时间为2ms。

Runtime: 2 ms, faster than 84.70% of Java online submissions for Find the Minimum Number of Fibonacci Numbers Whose Sum Is K.

Memory Usage: 37.1 MB, less than 100.00% of Java online submissions for Find the Minimum Number of Fibonacci Numbers Whose Sum Is K.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1414-find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k-解题思路分析/