LeetCode 题解工作台
和为 K 的最少斐波那契数字数目
给你数字 k ，请你返回和为 k 的斐波那契数字的最少数目，其中，每个斐波那契数字都可以被使用多次。 斐波那契数字定义为： F 1 = 1 F 2 = 1 F n = F n-1 + F n-2 ， 其中 n > 2 。 数据保证对于给定的 k ，一定能找到可行解。 示例 1： 输入： k = 7 …
2
题型
6
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
我们可以每次贪心地选取一个不超过 的最大的斐波那契数，然后将 减去该数，答案加一，一直循环，直到 $k = 0$ 为止。 由于每次贪心地选取了最大的不超过 的斐波那契数，假设为 ，前一个数为 ，后一个数为 。将 减去 ，得到的结果，一定小于 ，也即意味着，我们选取了 之后，一定不会选到 。这是因为，如果能选上 ，那么我们在前面就可以贪心地选上 的下一个斐波那契数 ，这不符合我们的假设。…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
给你数字 k ，请你返回和为 k 的斐波那契数字的最少数目，其中，每个斐波那契数字都可以被使用多次。
斐波那契数字定义为：
- F1 = 1
- F2 = 1
- Fn = Fn-1 + Fn-2 ， 其中 n > 2 。
数据保证对于给定的 k ，一定能找到可行解。
示例 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
解题思路
方法一：贪心
我们可以每次贪心地选取一个不超过 的最大的斐波那契数，然后将 减去该数，答案加一，一直循环，直到 为止。
由于每次贪心地选取了最大的不超过 的斐波那契数，假设为 ，前一个数为 ，后一个数为 。将 减去 ，得到的结果，一定小于 ，也即意味着，我们选取了 之后，一定不会选到 。这是因为，如果能选上 ，那么我们在前面就可以贪心地选上 的下一个斐波那契数 ，这不符合我们的假设。因此，我们在选取 之后，可以贪心地减小斐波那契数。
时间复杂度 ，空间复杂度 。
class Solution:
def findMinFibonacciNumbers(self, k: int) -> int:
a = b = 1
while b <= k:
a, b = b, a + b
ans = 0
while k:
if k >= b:
k -= b
ans += 1
a, b = b - a, a
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Assess if the candidate uses a greedy approach and justifies it effectively.
- question_mark
Look for a clear understanding of Fibonacci number generation and efficient use of them.
- question_mark
Check if the candidate ensures correctness by validating the final sum.
常见陷阱
外企场景- error
Failing to generate the correct Fibonacci sequence up to k.
- error
Choosing Fibonacci numbers that are too small, leading to excessive additions.
- error
Overcomplicating the problem by considering all possible combinations instead of using a greedy approach.
进阶变体
外企场景- arrow_right_alt
Allow only distinct Fibonacci numbers in the sum.
- arrow_right_alt
Limit the number of Fibonacci numbers that can be used in the sum.
- arrow_right_alt
Extend the problem to larger integers, requiring more advanced optimizations.