【贪心】B_5373.和为K的最少斐波那契数字数目（打表）

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

斐波那契数字定义为&＃xff1a;

• F1 &＃61; 1
  F2 &＃61; 1
  Fn &＃61; Fn-1 &＃43; Fn-2 &＃xff0c; 其中 n > 2 。

数据保证对于给定的 k &＃xff0c;一定能找到可行解。

提示&＃xff1a;1 <&＃61; k <&＃61; 10^9

输入&＃xff1a;k &＃61; 7
输出&＃xff1a;2
解释&＃xff1a;斐波那契数字为&＃xff1a;1&＃xff0c;1&＃xff0c;2&＃xff0c;3&＃xff0c;5&＃xff0c;8&＃xff0c;13&＃xff0c;……
对于 k &＃61; 7 &＃xff0c;我们可以得到 2 &＃43; 5 &＃61; 7 。输入&＃xff1a;k &＃61; 19
输出&＃xff1a;3
解释&＃xff1a;对于 k &＃61; 19 &＃xff0c;我们可以得到 1 &＃43; 5 &＃43; 13 &＃61; 19 。


方法一&＃xff1a;贪心

要求使用的数字最少&＃xff0c;意思就是让我们只能先用相对较大且接近 k 的数。我的做法是先预处理 fab&＃xff0c;然后从后往前枚举&＃xff0c;尽量使用大的数。

public int findMinFibonacciNumbers(int k) {List<Integer> fab &＃61; new ArrayList<>();fab.add(1);fab.add(1);while (fab.get(fab.size()-1) < k) {int t &＃61; fab.get(fab.size()-1) &＃43; fab.get(fab.size()-2); fab.add(t);}int cnt &＃61; 0;for (int i &＃61; fab.size()-1; i >&＃61; 0; i--) {while (k >&＃61; fab.get(i)) {k -&＃61; fab.get(i);cnt&＃43;&＃43;;} }return cnt;
}


复杂度分析

• 时间复杂度&＃xff1a;$O(n)$&＃xff0c;
• 空间复杂度&＃xff1a;$O(n)$&＃xff0c;