题目

类型：贪心

解题思路

利用斐波那契数列的递推性质
和
凑成 k 的最优解中不包含重复数字的结论

凑成 k 的最优解中不包含重复数字：

代码

class Solution {
    public int findMinFibonacciNumbers(int k) {
        int a = 1, b = 1;
        while (b <= k) {
            int c = a + b;
            a = b; b = c;
        }
        int ans = 0;
        while (k != 0) {
            if (k >= b) {
                k -= b; ans++;
            }
            int c = b - a;
            b = a; a = c;
        }
        return ans;
    }
}