Medium

题目描述

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

斐波那契数字定义为：

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

数据保证对于给定的约束条件，我们一定可以找到可行解。

示例 1：

输入：k = 7
输出：2
解释：斐波那契数字为：1, 1, 2, 3, 5, 8, 13, ...
对于 k = 7 ，我们可以使用 2 + 5 = 7.

示例 2：

输入：k = 10
输出：2
解释：对于 k = 10 ，我们可以使用 2 + 8 = 10.

示例 3：

输入：k = 19
输出：3
解释：对于 k = 19 ，我们可以使用 1 + 5 + 13 = 19.

提示：

  • 1 <= k <= 10^9

解题思路

这是一个经典的贪心算法题目。核心思想是利用斐波那契数列的特性和贪心策略。

核心观察： 根据 Zeckendorf 定理，任何正整数都可以表示为不连续斐波那契数的和，且这种表示是唯一的。更重要的是，贪心策略（每次选择不超过当前数的最大斐波那契数）能够得到最优解。

算法步骤：

  1. 首先生成所有不超过 k 的斐波那契数，由于 k ≤ 10^9，斐波那契数增长很快，最多只需要 44 个数
  2. 使用贪心策略：从最大的斐波那契数开始，如果当前斐波那契数不超过剩余的 k，就选择它
  3. 将 k 减去选中的斐波那契数，计数器加 1，继续这个过程直到 k 变为 0

为什么贪心策略有效： 斐波那契数列有个重要性质：F(n) = F(n-1) + F(n-2)，这意味着 F(n) > F(n-1) + F(n-2) + … + F(1)。因此选择最大可能的斐波那契数总是最优的，不会错过更好的组合。

时间复杂度为 O(log k)，因为斐波那契数的个数是对数级别的。

代码实现

class Solution {
public:
    int findMinFibonacciNumbers(int k) {
        vector<int> fibs;
        int a = 1, b = 1;
        fibs.push_back(a);
        
        while (b <= k) {
            fibs.push_back(b);
            int temp = a + b;
            a = b;
            b = temp;
        }
        
        int count = 0;
        for (int i = fibs.size() - 1; i >= 0 && k > 0; i--) {
            if (fibs[i] <= k) {
                k -= fibs[i];
                count++;
            }
        }
        
        return count;
    }
};

class Solution:
    def findMinFibonacciNumbers(self, k: int) -> int:
        fibs = []
        a, b = 1, 1
        fibs.append(a)
        
        while b <= k:
            fibs.append(b)
            a, b = b, a + b
        
        count = 0
        for i in range(len(fibs) - 1, -1, -1):
            if k == 0:
                break
            if fibs[i] <= k:
                k -= fibs[i]
                count += 1
        
        return count

public class Solution {
    public int FindMinFibonacciNumbers(int k) {
        List<int> fibs = new List<int>();
        int a = 1, b = 1;
        fibs.Add(a);
        
        while (b <= k) {
            fibs.Add(b);
            int temp = a + b;
            a = b;
            b = temp;
        }
        
        int count = 0;
        for (int i = fibs.Count - 1; i >= 0 && k > 0; i--) {
            if (fibs[i] <= k) {
                k -= fibs[i];
                count++;
            }
        }
        
        return count;
    }
}

var findMinFibonacciNumbers = function(k) {
    const fibs = [];
    let a = 1, b = 1;
    fibs.push(a);
    
    while (b <= k) {
        fibs.push(b);
        const temp = a + b;
        a = b;
        b = temp;
    }
    
    let count = 0;
    for (let i = fibs.length - 1; i >= 0 && k > 0; i--) {
        if (fibs[i] <= k) {
            k -= fibs[i];
            count++;
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小说明
时间复杂度O(log k)斐波那契数的个数约为 log k 个，生成和遍历都是 O(log k)
空间复杂度O(log k)存储斐波那契数列需要 O(log k) 空间