leetcode每日一题——和为K的最少斐波那契数字数目
目录
题目
题目详解
我开始是想着构造好fib数组的值，然后用背包问题去解决它。可惜，直接超时了！
后面直接用最简单的贪心方式没想到真的可行。。
然后看了题解才知道原来fib的「每次选择不超过当前 k 的最大数」这是一个特有的结论，然后大家都在证明他，虽然我看不懂，但我大受震撼😂
解题代码
class Solution {
public:
int findMinFibonacciNumbers(int k) {
vector<int>items(2,1);
int ret = 0;
while(items.back()<k){
items.push_back(items.back()+items[items.size()-2]);
}
for(int i=items.size()-1;i>=0;i--){
ret += k/items[i];
k %= items[i];
}
return ret;
}
};