题目大意：
和为 K 的最少斐波那契数字数目
给你数字 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
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1414
解题思路分析：
- 先求出小于k的所有斐波那契数字，存放至List中。
- 用k减去List中小于等于k的最大数字。
- 重复第二步，直到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-解题思路分析/