在C ++中找到总和为K的最小斐波那契数
假设我们有一个数字k，那么无论斐波那契数是否可以多次使用，我们都必须找到总和等于k的最小斐波那契数。
因此，如果输入像k=7，则输出将为2，因为斐波那契数为：1、1、2、3、5、8、13...对于k=7，我们可以使用2+5=7。
为了解决这个问题，我们将遵循以下步骤-
定义一个数组f
在f的末尾插入0
在f的末尾插入1
当f<=k的最后一个元素时-
将（f的最后一个元素+f的倒数第二个元素）插入f
ret：=0
j：=f的最后一个索引
而（j>=0并且k>0），做-
（将j减1）
k：=k-f[j]
（增加ret1）
如果f[j]<=k，则-
除此以外
返回ret
例
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findMinFibonacciNumbers(int k) {
vector<int> f;
f.push_back(0);
f.push_back(1);
while (f.back() <= k) {
f.push_back(f[f.size() - 1] + f[f.size() - 2]);
}
int ret = 0;
int j = f.size() - 1;
while (j >= 0 && k > 0) {
if (f[j] <= k) {
k -= f[j];
ret++;
}
else
j--;
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.findMinFibonacciNumbers(7));
}输入值
7
输出结果
2