1414. 和为 K 的最少斐波那契数字数目(贪心）

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

class Solution {
public:
    int findMinFibonacciNumbers(int k) {
        //unsigned
        long long f[92];
        f[1]=1;f[2]=1;
        if(k==1)
            return 1;
        int cnt=0;
        bool flag=false;
        for(int i=3;i<=50;i++)
        {
                f[i]=f[i-1]+f[i-2];
                //cout<<f[i]<<" ";
                if(k==f[i])
                {
                       cnt=1;
                       break;
                }
                if(f[i]>k)
                {
                    int sum=0;
                    for(int j=i-1;j>=1;j--)
                    {
                        if(sum+f[j]<=k)
                            {
                                sum+=f[j];
                                cnt++;
                                if(sum==k)
                                   {
                                       flag=true;break;
                                   }
                            }

                    }
                    if(flag)
                        break;
                }  
        }
        return cnt;
    }
};