【算法编程】和为 K 的最少斐波那契数字数目

【算法编程】和为 K 的最少斐波那契数字数目

  给定k个数，其满足斐波那契性质，从中挑选一部分数字（每个数只能被挑选1次）使得它们的和恰巧为k。目标是求出最少能够挑选几个数满足这个条件。k取值范围为

  试题来源： ​​LeetCode.1414​​

  难度：★★★☆☆

【输入】k=7
【输出】2
【解析】斐波那契数字为：1，1，2，3，5，8，13，……，对于 k = 7 ，我们可以得到 2 + 5 = 7 。

C++源代码：

class Solution {
  public:
      int findMinFibonacciNumbers(int k) {
          int ans=0, i=2;
          vector<int> dp(2,1);
          for(i=2; i<=k; i++) {
              dp.push_back(dp[i-1] + dp[i-2]);
              if(dp[i] > k) break;
          }
          for(i=dp.size()-1; i>=0; i--){
              if(k >= dp[i]){
                  k-=dp[i];
                  ans++;
              }
          }
          return ans;    
      }
  };

原理讲解：

（1）斐波那契数列定义为：

其中 且 ，。

（2）为了能够找到合适的解，首先我们可知数列一定是升序排列的，因此我们可以再没添加一个数时，去判断其是否比k值大，因为如果后面的数比k大，则其不可能与前面任意几个数相加等于k，所以这里可以作为一个减少额外运算的优化点；

（3）因为数列是升序排列，因为目标是尽可能找到最少的数使之和为k，因此只需要从最后一个数向前遍历，依次选择，直到满足累计的和为k即可。每一次累计时，设置一个ans变量来保存数字的数量，而此时k减去对应的值。经过分析可知，我们可以找到唯一的最优解。

知识点：
动态规划

其他解法：

class Solution {
        int f[45];
    public:
        int findMinFibonacciNumbers(int k) {
            int i,ans=0;
            for(f[1]=1,i=2;i<45;i++)f[i]=f[i-1]+f[i-2];
            for(i=44;i;i--)if(k>=f[i])
            {
                k-=f[i];
                ans++;
            }
            return ans;
        }
    };