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

题目描述

这是 LeetCode 上的 1414. 和为 K 的最少斐波那契数字数目 ,难度为 中等

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

斐波那契数字定义为:

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

数据保证对于给定的 k ,一定能找到可行解。

示例 1:

1
2
3
4
5
6
输入:k = 7

输出:2

解释:斐波那契数字为:1,1,2,3,5,8,13,……
对于 k = 7 ,我们可以得到 2 + 5 = 7

示例 2:
1
2
3
4
5
输入:k = 10

输出:2

解释:对于 k = 10 ,我们可以得到 2 + 8 = 10

示例 3:
1
2
3
4
5
输入:k = 19

输出:3

解释:对于 k = 19 ,我们可以得到 1 + 5 + 13 = 19

提示:

  • $1 <= k <= 10^9$

打表 + 贪心 + 二分

利用 k 的数据范围为 $1 <= k <= 10^9$,可以先使用 static 进行打表,预处理出值不超过 $10^9$ 的斐波那契数,存入数组 list 中。

然后考虑如何使用 list 中的数字(可重复)凑成 k

一个直观的想法是:每次从 list 中找到不超过 k 的最大数,用于进行对 k 的消减,直到 k 被消减到 $0$ 为止,消减的次数即是答案。

而「从 list 中找到不超过 k 的最大数」这一操作,可使用「二分」。

下面证明该做法的正确性:

假定该做法所得到的可行解序列为 A(序列长度为 $ans$),真实最优解序列为 B(序列长度为 $min$)。

假设两者长度不等(只能是 $ans > min$),这意味着我们将 AB 之间的相同的元素去掉后,剩余元素序列有如下结论:

  • A 序列剩余元素之和」等于「B 序列剩余元素之和」;
  • A 序列剩余元素个数」大于「B 序列剩余元素个数」。

A'A 的剩余元素序列,B'B 的剩余元素序列。

我们知道 A' 中的最大数必然大于 B' 中的最大数。不可能是等于关系(相等元素均被去掉),也不可能是小于关系,否则在构造 A 序列的时候就会按照生成 B 序列的方向进行构造。

但要只靠该性质,要证明不存在满足上述结论的斐波那契数组合仍是困难。

我们可以从「斐波那契数」性质出发,挖掘可行解 A 的某些性质,然后证明不存在不满足该性质的方案比 A 更优即可。

对于可行解 A 而言,由于我们「每次都选择不超过当前 k 的最大数」,因此必然可行解中必然不存在两项相邻的斐波那契数,否则会在选择 $fi$ 和 $f{i+1}$ 之前先因为「每次都选择不超过当前 k 的最大数」而先选择 $f_{i+2}$。

同时,由于 $fi=f{i-1}+f{i-2}$、$f{i+1}=f{i}+f{i-1}$ 和 $f{i+2}=f{i+1}+f{i}$ 可得 $2 * f{i}=f{i+1}+f{i-2}$。

也就是说可行解 A 中必然不会出现相同值,否则会在选择 $fi$ 之前先因为「每次都选择不超过当前 k 的最大数」而先选择 $f{i+1}$。

该推理对于边界特殊值 $1$ 同样成立,如果可行解 A 中存在多个 $1$,则必然会先因为「每次都选择不超过当前 k 的最大数」选择 $f_3=2$。

再根据「斐波那契数奇偶数项求和」可知:$a1 + a_3 + … + a{2n - 1} = a{2n}$ 和 $a_2 + a_4 + … + a{2n} = a_{2n+1} - 1$。

综上,可以证明不存在比可行解 A 更短的最优解。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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^9$ 的斐波那契数的数量为 C,复杂度为 $O(\log{k} * \log{C})$
  • 空间复杂度:$O(C)$

贪心

上述做法,由于预处理了所有值不超过 $10^9$ 的斐波那契数,导致无法直接取得「值不超过 k 的最大数」,需要再套一层「二分」。

不采用预处理的方式,利用斐波那契数列的递推性质,以及凑成 k 的最优解中不包含重复数字的结论,我们可以做到 $O(\log{k})$ 时间复杂度和 $O(1)$ 空间复杂度。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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(1)$

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1414 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。