企业电子商务网站开发数据库设计,微网站建设价格,淘宝客网站建站教程,ai绘制logo给你数字 k #xff0c;请你返回和为 k 的斐波那契数字的最少数目#xff0c;其中#xff0c;每个斐波那契数字都可以被使用多次。
斐波那契数字定义为#xff1a;
F1 1 F2 1 Fn Fn-1 Fn-2 #xff0c; 其中 n 2 。 数据保证对于给定的 k #xff0c;一定能找…给你数字 k 请你返回和为 k 的斐波那契数字的最少数目其中每个斐波那契数字都可以被使用多次。
斐波那契数字定义为
F1 1 F2 1 Fn Fn-1 Fn-2 其中 n 2 。 数据保证对于给定的 k 一定能找到可行解。
示例 1
输入k 7 输出2 解释斐波那契数字为11235813…… 对于 k 7 我们可以得到 2 5 7 。
代码
class Solution {public int findMinFibonacciNumbers(int k) {LinkedListInteger list new LinkedList();list.add(1);int a 1, b 1, c 0,res0;while (true) {//计算出小于k的数列c a b;a b;b c;if (c k) break;list.add(c);}int ilist.size()-1;while (k 0)//从右到左贪心{if(list.get(i)k) {i--;continue;}k-list.get(i);//减去已经找到了的数字缩小规模res;i--;}return res;}
}
