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

题目描述链接：https://leetcode-cn.com/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k/

解题思路：基本算法，贪心。此题要求返回和为k的最小斐波那契数字数目，且可以重复使用，所以只需选择斐波那契数字中

小于k的最大数字，并用两者的差值更新k，然后继续迭代即可。

具体LeetCode C++求解如下：

class Solution {
public:
    int findMinFibonacciNumbers(int k) {
        if(k==1||k==2||k==3){
            //前几项在后面代码并不能找到F[i]>k,需特判。而k==4或5正好i可更新到5或6；
            return 1;
        }
        int F[1000];
        F[1]=1;
        F[2]=1;
        int i;
        for(i=3;i<=k;i++){
           F[i]=F[i-1]+F[i-2];
           if(F[i]>k){
               break;
           }
        }
      //  printf("%d,%d",i,F[i]);
        //F[i-1]<=k,我们从大到小选择和为k，可以保证最少
        int times=0;
        for(int j=i-1;j>=1;j--){
              if(k-F[j]<0){
                  continue;
              }
              else if(k-F[j]==0){
                  times++;
                  return times;
              }
              else{
                  while(k-F[j]>0){
                     k-=F[j];
                     times++;

                     //printf("times=%d",times);
                  }

              }
              
        }
        return times;
    }
};