一、描述

给你数字 k ，请你返回和为 k 的斐波那契数字的最少数目，其中，每个斐波那契数字都可以被使用多次。
输入：k = 7 输出：2
解释：斐波那契数字为：1，1，2，3，5，8，13，……
对于 k = 7 ，我们可以得到 2 + 5 = 7
//数据保证对于给定的 k ，一定能找到可行解
//1 <= k <= 10^9

二、解

找到斐波那契数列中能构成给定数k的最少数字个数
最少数字个数（每次取=k的数，没有就取小于k的第一个数（最大的））
有等于k的数，返回个数（=循环次数）
没有=k的数时，k=k-取小于k的第一个数，继续循环找k
循环：

public static void main(String[] args) {System.out.println(findMinFibonacciNumbers(7));}public static int findMinFibonacciNumbers(int k) {int num1 = 1, num2 = 1, temp = 0, i = 1;while (true) {//找到第一个大于或等于k的数while (num2 <= k) {if (num2 == k) {return i;}temp = num2;num2 = num2 + num1;num1 = temp;}//没有和k相等的数//个数++i++;//num2>k num1<k 所以 k-num1k = k - num1;num1 = 1;num2 = 1;}}

递归：

public static int findMinFibonacciNumbers(int k) {if (k==0) {return 0;}int a = 1,b = 1;while(a+b<=k){int c = a+b;a = b;b = c;}return findMinFibonacciNumbers(k-b)+1;}

其他方法
打表：构建<10^9的斐波那契数，直接带k去list找，直到k=0；
二分

三、Tips

斐波那契数列：F(n) = F(n-1)+F(n-2) F(0)=1 F(1) = 1
1，1，2，3，5，8，13，……
这道题m应该是在证明取第一个小于k的数构成k所需数字个数最少，不是直接解出，推荐食用官方证明