题目描述
这是 LeetCode 上的 1414. 和为 K 的最少斐波那契数字数目 ，难度为 中等。
Tag : 「数学」、「二分」、「贪心」
给你数字 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^91<=k<=109
打表 + 贪心 + 二分
利用 k 的数据范围为 1 <= k <= 10^91<=k<=109，可以先使用 static 进行打表，预处理出值不超过 10^9109 的斐波那契数，存入数组 list 中。
然后考虑如何使用 list 中的数字（可重复）凑成 k。
一个直观的想法是：每次从 list 中找到不超过 k 的最大数，用于进行对 k 的消减，直到 k 被消减到 00 为止，消减的次数即是答案。
而「从 list 中找到不超过 k 的最大数」这一操作，可使用「二分」。
下面证明该做法的正确性：
假定该做法所得到的可行解序列为 A（序列长度为 ansans），真实最优解序列为 B（序列长度为 minmin）。
假设两者长度不等（只能是 ans > minans>min），这意味着我们将 A 和 B 之间的相同的元素去掉后，剩余元素序列有如下结论：
- 「
A序列剩余元素之和」等于「B序列剩余元素之和」； - 「
A序列剩余元素个数」大于「B序列剩余元素个数」。
A' 为 A 的剩余元素序列，B' 为 B 的剩余元素序列。
我们知道 A' 中的最大数必然大于 B' 中的最大数。不可能是等于关系（相等元素均被去掉），也不可能是小于关系，否则在构造 A 序列的时候就会按照生成 B 序列的方向进行构造。
但要只靠该性质，要证明不存在满足上述结论的斐波那契数组合仍是困难。
我们可以从「斐波那契数」性质出发，挖掘可行解 A 的某些性质，然后证明不存在不满足该性质的方案比 A 更优即可。
对于可行解 A 而言，由于我们「每次都选择不超过当前 k 的最大数」，因此必然可行解中必然不存在两项相邻的斐波那契数，否则会在选择 f_ifi 和 f_{i+1}fi+1 之前先因为「每次都选择不超过当前 k 的最大数」而先选择 f_{i+2}fi+2。
同时，由于 f_i=f_{i-1}+f_{i-2}fi=fi−1+fi−2、f_{i+1}=f_{i}+f_{i-1}fi+1=fi+fi−1 和 f_{i+2}=f_{i+1}+f_{i}fi+2=fi+1+fi 可得 2 * f_{i}=f_{i+1}+f_{i-2}2∗fi=fi+1+fi−2。
也就是说可行解 A 中必然不会出现相同值，否则会在选择 f_ifi 之前先因为「每次都选择不超过当前 k 的最大数」而先选择 f_{i+1}fi+1。
该推理对于边界特殊值 11 同样成立，如果可行解 A 中存在多个 11，则必然会先因为「每次都选择不超过当前 k 的最大数」选择 f_3=2f3=2。
再根据「斐波那契数奇偶数项求和」可知：a_1 + a_3 + ... + a_{2n - 1} = a_{2n}a1+a3+...+a2n−1=a2n 和 a_2 + a_4 + ... + a_{2n} = a_{2n+1} - 1a2+a4+...+a2n=a2n+1−1。
综上，可以证明不存在比可行解 A 更短的最优解。
代码：
class Solution { static List<Integer> list = new ArrayList<>(); static { list.add(1); int a = 1, b = 1; while (b <= (int)1e9) { int c = a + b; a = b; b = c; list.add(c); } } public int findMinFibonacciNumbers(int k) { int ans = 0; while (k != 0) { int l = 0, r = list.size() - 1; while (l < r) { int mid = l + r + 1 >> 1; if (list.get(mid) <= k) l = mid; else r = mid - 1; } k -= list.get(r); ans++; } return ans; } } 复制代码
- 时间复杂度：令值不超过 10^9109 的斐波那契数的数量为
C，复杂度为 O(\log{k} * \log{C})O(logk∗logC) - 空间复杂度：O(C)O(C)
贪心
上述做法，由于预处理了所有值不超过 10^9109 的斐波那契数，导致无法直接取得「值不超过 k 的最大数」，需要再套一层「二分」。
不采用预处理的方式，利用斐波那契数列的递推性质，以及凑成 k 的最优解中不包含重复数字的结论，我们可以做到 O(\log{k})O(logk) 时间复杂度和 O(1)O(1) 空间复杂度。
代码：
class Solution { public int findMinFibonacciNumbers(int k) { int a = 1, b = 1; while (b <= k) { int c = a + b; a = b; b = c; } int ans = 0; while (k != 0) { if (k >= b) { k -= b; ans++; } int c = b - a; b = a; a = c; } return ans; } } 复制代码
- 时间复杂度：O(\log{k})O(logk)
- 空间复杂度：O(1)O(1)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1414 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
