---

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

• 标签：贪心、数学
• 难度：中等

题目链接

• 1414. 和为 K 的最少斐波那契数字数目 - 力扣

题目大意

描述：给定一个整数 $k$。

要求：返回和为 $k$ 的最少斐波那契数字的数目。每个斐波那契数字可以使用多次。

说明：

• $1 \le k \le 10^9$。

示例：

• 示例 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 。

解题思路

思路 1：贪心

1. 核心思想

Zeckendorf 定理：任何正整数可以表示为若干个不连续的斐波那契数之和。且贪心地选取不超过当前剩余值的最大的斐波那契数，可以得到最优解（使用数最少）。

2. 具体步骤

第 1 步：生成不超过 $k$ 的所有斐波那契数列表 $fib$（$F_1=1, F_2=1, F_n=F_{n-1}+F_{n-2}$）。

第 2 步：从大到小遍历 $fib$，每次取不超过当前 $k$ 的最大数，$k$ 减去该数，计数 $+1$。

第 3 步：当 $k=0$ 时停止，返回计数。

3. 正确性证明

贪心选择性质：选尽可能大的斐波那契数不会影响后续选择。因为斐波那契数满足 $F_{n+2} > 2 \times F_n$（可证明），所以选最大数不会导致后续无法凑出（跳过 $F_n$ 意味着要用至少两个 $F_{n-1}$ 来替代，不更优）。

4. 举例说明

以 $k=19$ 为例：

斐波那契数列 $\le 19$：$1,1,2,3,5,8,13$

贪心过程：

• $19$：最大 $\le 19$ 的数是 $13$，剩余 $6$，计数 $1$
• $6$：最大 $\le 6$ 的数是 $5$，剩余 $1$，计数 $2$
• $1$：取 $1$，剩余 $0$，计数 $3$

最少 $3$ 个：$13 + 5 + 1 = 19$。

思路 1：代码

class Solution:
    def findMinFibonacciNumbers(self, k: int) -> int:
        # 生成斐波那契数列
        fib = [1, 1]
        while fib[-1] <= k:
            fib.append(fib[-1] + fib[-2])
        fib.pop()  # 去掉超过 k 的最后一个

        count = 0
        for f in reversed(fib):
            if f <= k:
                k -= f
                count += 1
                if k == 0:
                    break

        return count

思路 1：复杂度分析

• 时间复杂度：$O(\log k)$，斐波那契数列指数增长，项数 $O(\log k)$。
• 空间复杂度：$O(\log k)$，存储斐波那契数列。