class Solution { public: int findMinFibonacciNumbers(int k) { vector<int> fibo; fibo.push_back(1); fibo.push_back(1); while(true){ int i=fibo[fibo.size()-1]+fibo[fibo.size()-2]; if(i>k) break; fibo.push_back(i); } int res=0; while(k>0){ res++; int cur=search(k,fibo); k-=fibo[cur]; } return res; } int search(int sum, vector<int>& fibo){ int left=0; int right=fibo.size()-1; while(left<=right){ int mid=(left+right)/2; if(fibo[mid]<=sum) left=mid+1; else right=mid-1; } return right; } };
证明：
https://proofwiki.org/wiki/Zeckendorf%27s_Theorem
https://proofwiki.org/wiki/Sum_of_Non-Consecutive_Fibonacci_Numbers