每日一题(2022-02-03):和为 K 的最少斐波那契数字数目

每日一题(2022-02-03):和为 K 的最少斐波那契数字数目

来源:力扣
难度:中等
题目:1414. 和为 K 的最少斐波那契数字数目

题目详情

原题截图.png

题解思路

几乎纯粹是数学思路,只需要证明每次都选取不超过K的最大斐波那契数字就能满足题目要求,剩下的代码实现就很简单了;
详见官方题解一:贪心
官方题解图一.png
官方题解图二.png

代码结果

class Solution {
public:
    int findMinFibonacciNumbers(int k) {
        vector<int> vecFibNums;
        vecFibNums.push_back(1);
        int a = 1, b = 1;
        while (a + b <= k)
        {
            int c = a + b;
            vecFibNums.push_back(c);
            a = b, b = c;
        }

        int ans = 0;
        for (int i = vecFibNums.size() - 1; i >= 0 && k > 0; --i)
        {
            if (k >= vecFibNums[i])
            {
                k -= vecFibNums[i];
                ++ans;
            }
        }

        return ans;
    }
};

运行结果.png