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

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

斐波那契数字定义为：

F1 = 1
F2 = 1
Fn = Fn-1 + Fn-2 ， 其中 n > 2 。
数据保证对于给定的 k ，一定能找到可行解。

题目链接：1414. 和为 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

解题思路：

定义一个全局的vector，然后自己写一个函数用来求斐波那契数列一些数的值，然后将这些值放到vector里面，vector里面的最后一个值是在斐波那契数列里面大于k的最小值，即第一个大于k的值。

定义一个变量ans，用来记录需要几个斐波那契数字相加才能得到k

由于斐波那契数列中的数字是非递减序列，因此我们可以采用二分的方法来做.

每次通过二分找出最接近k(<=k)的那个值，然后再将我们的k减去这个值，更新k的值，然后再让ans++。

只要我们的k不等于0，我们就继续用二分去找最接近现在这个k的值，直到我们的k等于0为止。

代码：

class Solution {vector<int>f;
public://自己写个求斐波那契数列的函数void creat_f(int k){f.push_back(1);f.push_back(1);int a = 1;int b = 1;int c = 0;while(c<=k){c = a+b;b = a;a = c;f.push_back(c);}}int findMinFibonacciNumbers(int k) {creat_f(k);int ans = 0;while(k!=0){//通过二分查找到每次最接近k的值int left = 0,right = f.size()-1;while(left<right){//这里要向上取整int mid = (left+right+1)>>1;//如果mid下标值大于k//证明我们要找的最接近k的值在[left,mid]这个区间里面，包括midif(f[mid]<=k){left = mid;}//反之在[left,mid-1]这个区间里面else{right = mid-1;}}//每次二分完更新k的值k-=f[right];ans++;}return ans;}
};