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

链接：1414.和为K的最少斐波那契数字数目
难度：Medium
标签：贪心、数学
简介：给你数字 k ，请你返回和为 k 的斐波那契数字的最少数目，其中，每个斐波那契数字都可以被使用多次。

题解 1 - cpp

• 编辑时间：2022-02-03
• 内存消耗：5.9MB
• 编程语言：cpp
• 解法介绍：贪心策略。

int fib[] = {1,         1,        2,        3,         5,         8,
             13,        21,       34,       55,        89,        144,
             233,       377,      610,      987,       1597,      2584,
             4181,      6765,     10946,    17711,     28657,     46368,
             75025,     121393,   196418,   317811,    514229,    832040,
             1346269,   2178309,  3524578,  5702887,   9227465,   14930352,
             24157817,  39088169, 63245986, 102334155, 165580141, 267914296,
             433494437, 701408733};
class Solution {
   public:
    int findMinFibonacciNumbers(int k) {
        int cnt = 0;
        for (int idx = 43; k; idx--) {
            while (fib[idx] > k) idx--;
            cnt += k / fib[idx];
            k %= fib[idx];
        }
        return cnt;
    }
};