【Description】
给你数字 k ，请你返回和为 k 的斐波那契数字的最少数目，其中，每个斐波那契数字都可以被使用多次。
斐波那契数字定义为：
F1 = 1
F2 = 1
Fn = Fn-1 + Fn-2 ， 其中 n > 2 。
数据保证对于给定的 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 <= 10^9
【Idea】
因为斐波那契数的特点是：每一个数是前两个数的和。所以求和项重复使用两次时就可以由他的前后项代替，因此可以用逆序贪心求解。
先找到一个最大值不大于k的斐波那契数列；
之后借助两个tag值逆向贪心遍历，一个s标记当前遍历的目标和值，另一个cnt标记当前和的数目。
如果-当前遍历数仍>0，就判定该数可以作为组成和k的一项，否则continue
直到s==0。
【Solution】
class Solution:
def get_fib(self, k):
fibs = [1, 1]
while True:
tp = fibs[-1] + fibs[-2]
if tp > k:
break
else:
fibs.append(tp)
return fibs
def findMinFibonacciNumbers(self, k: int) -> int:
fibs = self.get_fib(k) # 取得不大于k的所有斐波那契数
s = k
idx = len(fibs)-1
cnt = 0
while s > 0:
if s - fibs[idx] >=0:
s -= fibs[idx]
cnt += 1
idx -= 1
return cnt
截屏2020-06-28 上午12.21.38.png
