在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]

• （增加ret 1）

• 如果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