给你数字 k ,请你返回和为 k 的斐波那契数字的最少数目,其中,每个斐波那契数字都可以被使用多次。
斐波那契数字定义为:
数据保证对于给定的 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 的组成数字都有离它最近的斐波那契数字,只要每次找到离它最近的斐波那契数字,然后 k 减去最近的斐波那契数字,再继续找新 k 的最近斐波那契数字,直到 k 为 0,那么找的次数就为最少数目,用一个递归可以轻松解决。但是这些思路都是建立在 k 的组成数字一定有离它最近的数 的基础上,接下来我们来证明这个条件是正确的:
令离 k 最近的数为 Fn,易证 k 的组成一定不含连续数字,因为连续数字加起来就是一个新的斐波那契数字,所以假设 k 的组成不含 Fn,那么 k 的最大值 max 满足:
下面考虑重复的情况:
因此,无论什么情况,k 的组成数字一定有离它最近的斐波那契数字。
时间复杂度:O(log n)
空间复杂度:O(log n)
class Solution { public int findMinFibonacciNumbers(int k) { //如果 k 为 0,返回 0 if(k == 0){ return 0; } //定义当前值,上一值,辅助变量 int cur = 1, pre = 1, temp = 2; //给数组赋值 while(cur <= k){ //计算新的值 temp = cur + pre; //上一值变为当前值 pre = cur; //当前值变为新的值 cur = temp; } //k 减去上一值,继续递归遍历 return findMinFibonacciNumbers(k - pre) + 1; } }
方法2:贪心+迭代
因为 方法1 每次递归都要重复创建斐波那契数列,比较浪费时间,为避免这种情况,我们可以用迭代的方式。因为找斐波那契数列的时候我们定义了记录上一值的变量,那么我们可以反编译斐波那契数列,如果 k 的值大于当前数字,就减去当前数字,继续遍历,直到 k 为 0,然后返回减去的次数即可。
时间复杂度:O(log n)
空间复杂度:O(log n)
class Solution { public int findMinFibonacciNumbers(int k) { //定义当前值,上一值,辅助变量 int cur = 1, pre = 1, temp = 2; //给数组赋值 while(cur <= k){ //计算新的值 temp = cur + pre; //上一值变为当前值 pre = cur; //当前值变为新的值 cur = temp; } //记录数目 int count = 0; //反编译斐波那契数列 while(k > 0){ //当前数字小于等于 k,k 减去当前数字 if(cur <= k){ k -= cur; count++; } //计算上上一值 temp = cur - pre; //当前值变为上一值 cur = pre; //上一值变为上上一值 pre = temp; } //返回计数结果 return count; } }
题目来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k