原文链接: https://leetcode-cn.com/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k
英文原文
Given an integer k, return the minimum number of Fibonacci numbers whose sum is equal to k. The same Fibonacci number can be used multiple times.
The Fibonacci numbers are defined as:
F1 = 1F2 = 1Fn = Fn-1 + Fn-2forn > 2.
k.
Example 1:
Input: k = 7 Output: 2 Explanation: The Fibonacci numbers are: 1, 1, 2, 3, 5, 8, 13, ... For k = 7 we can use 2 + 5 = 7.
Example 2:
Input: k = 10 Output: 2 Explanation: For k = 10 we can use 2 + 8 = 10.
Example 3:
Input: k = 19 Output: 3 Explanation: For k = 19 we can use 1 + 5 + 13 = 19.
Constraints:
1 <= k <= 109
中文题目
给你数字 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
通过代码
高赞题解
方法一：贪心
分析
我们构造出所有小于等于 $k$ 的斐波那契数，随后贪心地从大到小选取即可。
正确性证明
我们只需要证明：
对于任意给定的 $k$，存在一种最优的选择方法，其中我们选择了不超过 $k$ 的最大斐波那契数。
如果我们可以证明上述结论，那么对于给定的 $k$，我们就可以选择不超过 $k$ 的最大斐波那契数。剩下的和为 $k_0$，我们继续选择不超过 $k_0$ 的最大斐波那契数。以此类推，就是我们上文「分析」中的贪心选取方法。
那么我们如何证明这个结论呢？证明的过程分为三步，感兴趣的读者可以仔细阅读：
第一步：证明 我们不会选取连续两个斐波那契数。
我们用 $F_i$ 表示第 $i$ 个斐波那契数。假设我们选取了 $F_x$ 和 $F_{x+1}$，根据斐波那契数的定义，有：
$$
F_{x+2} = F_x + F_{x+1}
$$因此我们可以用第 $x+2$ 个斐波那契数替代它们，选择的数目减少一，得到了更优的答案。
第二步：证明 我们不会选取同一个斐波那契数超过一次。
假设我们选取了至少两次 $F_x$。如果 $x \leq 2$，那么我们可以用 $F_3=2$ 来替代两个 $F_x=1$；如果 $x>1$，那么我们可以用 $F_{x-2}$ 和 $F_{x+1}$ 来替代两个 $F_x$，选择的数目不变，这是因为：
$$
2F_x = F_{x-2} + F_{x-1} + F_x = F_{x-2} + F_{x+1}
$$并且有更大的可能通过「第一步」得到更优的答案。
第三步：证明我们需要的结论，即 对于任意给定的 $k$，我们需要选择不超过 $k$ 的最大斐波那契数。
假设不超过 $k$ 的最大斐波那契数为 $F_m$，但我们没有选择它，而是在 $F_1, F_2, \cdots, F_{m-1}$ 中进行选择。根据我们「第一步」和「第二步」的证明，我们不会选取连续两个斐波那契数，并且同一个数只会选取最多一次。因此我们用 $F_1, F_2, \cdots, F_{m-1}$ 能够构造出的最大数为：
$$
\begin{cases}
x_m &=& F_{m-1} + F_{m-3} + F_{m-5} + \cdots + F_4 + F_2 &, 当 m 为偶数 \
x_m &=& F_{m-1} + F_{m-3} + F_{m-5} + \cdots + F_3 + F_1 &, 当 m 为奇数
\end{cases}
$$当 $m$ 为奇数时，等式的值为：
$$
\begin{aligned}
x_m &= F_{m-1} + F_{m-3} + F_{m-5} + \cdots + F_4 + F_2 + F_1 - F_1\
&= F_{m-1} + F_{m-3} + F_{m-5} + \cdots + F_4 + F_3 - F_1\
&= F_{m-1} + F_{m-3} + F_{m-5} + \cdots + F_5 - F_1\
&= \cdots = F_m - 1\
&< F_m
\end{aligned}
$$它们无法构造出大于等于 $F_m$ 的数，也就无法构造出 $k$ 了。因此我们必须选择 $F_m$。
当 $m$ 为偶数时，等式的值为：
$$
\begin{aligned}
x_m &= F_{m-1} + F_{m-3} + F_{m-5} + \cdots + F_3 + F_1\
&= F_{m-1} + F_{m-3} + F_{m-5} + \cdots + F_3 + F_2\
&= F_{m-1} + F_{m-3} + F_{m-5} + \cdots + F_4\
&= \cdots = F_m
\end{aligned}
$$它们的和恰好等于 $F_m$。因此不如直接选择 $F_m$，这样选择的数目可以减少。
这样以来，对于任意给定的 $k$，我们选择不超过 $k$ 的最大斐波那契数 $F_m$ 总是更优的。
[sol1-C++]class Solution { public: int findMinFibonacciNumbers(int k) { int a = 1, b = 1; vector<int> fibo = {a, b}; while (a + b <= k) { fibo.push_back(a + b); int c = a + b; a = b; b = c; } int ans = 0; for (int i = fibo.size() - 1; i >= 0; --i) { if (k >= fibo[i]) { ++ans; k -= fibo[i]; } } return ans; } };
[sol1-Java]class Solution { public int findMinFibonacciNumbers(int k) { int a = 1, b = 1; List<Integer> fibo = new ArrayList<Integer>(Arrays.asList(a, b)); while (a + b <= k) { fibo.add(a + b); int c = a + b; a = b; b = c; } int ans = 0; for (int i = fibo.size() - 1; i >= 0; --i) { if (k >= fibo.get(i)) { ++ans; k -= fibo.get(i); } } return ans; } }
[sol1-Python3]class Solution: def findMinFibonacciNumbers(self, k: int) -> int: a = b = 1 fibo = [a, b] while a + b <= k: fibo.append(a + b) a, b = b, a + b ans = 0 for num in fibo[::-1]: if k >= num: ans += 1 k -= num return ans
复杂度分析
时间复杂度：$O(44)$。不超过 $10^9$ 的斐波那契数一共有 $44$ 个。
空间复杂度：$O(44)$。
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 7635 | 12627 | 60.5% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
