这篇题解围绕 LeetCode“和为 K 的最少斐波那契数目”展开，给出了从错误思路到可行贪心的推导过程。解题思路演进起初尝试背包式动态规划，但在题目约束下会超时。随后改用贪心策略，结果可通过。关键转折是识别出该题的斐波那契特有性质。核心结论每一步都选取不超过当前 k 的最大斐波那契数。选中后从 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; } };