题目

给你数字 k ，请你返回和为 k 的斐波那契数字的最少数目，其中，每个斐波那契数字都可以被使用多次。

斐波那契数字定义为：

F1 = 1
F2 = 1
Fn = Fn-1 + Fn-2 ，其中 n > 2 。

数据保证对于给定的 k ，一定能找到可行解。

来源：力扣（LeetCode）

解答

模拟法来找个数。

如果给定数字k，在斐波那契数列中，要找相加得到k最小的次数，一定是找小于等于k、且是斐波那契数列中最大的那个值，如{1,1,2,3,5}，给定k=4，那一定是找3这个数。然后再通过4-3=1，找1即可。

所以算法步骤为：

给定k；
通过斐波那契数列，一直找到比k第一个大的那个数为止，建立一个数组；
找到比k小的最少的那个数，然后求差继续找，且查找次数+1；
循环查找直至差为0；
返回查找次数。


class Solution {
private:
    vector<int> Fibonacci{1, 1, 2};

    // 首次调用，作用同findNum，因为一次建立Fibonacci数组，减少计算量。
    int fillFibonacci(int k) {
        int a = Fibonacci[0];
        int b = Fibonacci[1];
        int ret = Fibonacci[2];

        while (true) {
            a = b;
            b = ret;
            ret = a + b;
            Fibonacci.push_back(ret);
            if (ret > k) {
                break;
            }
        }

        return b;
    }

    // 只负责找比k小的那个值x，且x的下一个值比k大
    int findNum(int k) {
        if (k <= 3) {
            return k;
        }

        for (int i = 0; i < Fibonacci.size(); ++i) {
            if (Fibonacci[i] > k) {
                if (i == 0) {
                    return 1;
                }
                return Fibonacci[i - 1];
            }
        }

        return Fibonacci[Fibonacci.size() - 1];
    }

public:
    int findMinFibonacciNumbers(int k) {
        if (k <= 3) {
            return 1;
        }

        int get = 0;
        int ret = 0;
        int find = 0;

        get = fillFibonacci(k);
        ret++;
        find = k - get;

        while (find) {
            get = findNum(find);
            ret++;
            find -= get;
        }

        return ret;
    }
};

更好的方法请参考官方解法。

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

题目

解答