1414_和为k的最少斐波那契数字数目

难度：中等

题目

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

斐波那契数字定义为：

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

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

示例

示例一：

输入：k = 7
输出：2
解释：斐波那契数字为：1，1，2，3，5，8，13，……
对于 k = 7 ，我们可以得到 2 + 5 = 7 。

示例二：

输入：k = 10
输出：2
解释：对于 k = 10 ，我们可以得到 2 + 8 = 10 。

示例三：

输入：k = 19
输出：3
解释：对于 k = 19 ，我们可以得到 1 + 5 + 13 = 19 。

提示

  • 1 <= k <= 10^9

解题

题目要求返回和为 k 的斐波那契数字的最少数目，根据斐波那契定义，第三项为前两项的和，所以为了找到最小数目，只需要将最大项不超过 k 的斐波那契数列从后向前遍历，相加找到小于 k 的数字即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int findMinFibonacciNumbers(int k) {
  List<Integer> fib = new ArrayList<>();
  int a=1, b=1;
  fib.add(a);
  fib.add(b);
  while (a+b<=k){
    int c = a+b;
    fib.add(c);
    a=b;
    b=c;
  }
  int ans = 0;
  for (int i=fib.size()-1;i>=0;i--){
    while (k>=fib.get(i)&&k>0){
      k-=fib.get(i);
      ans++;
    }
  }
  return ans;
}