1414. 和为 K 的最少斐波那契数字数目

【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