【Description】
給你數(shù)字 k ，請你返回和為 k 的斐波那契數(shù)字的最少數(shù)目，其中，每個斐波那契數(shù)字都可以被使用多次。

斐波那契數(shù)字定義為：

F1 = 1
F2 = 1
Fn = Fn-1 + Fn-2 ， 其中 n > 2 。
數(shù)據(jù)保證對于給定的 k ，一定能找到可行解。

示例 1：

輸入：k = 7
輸出：2
解釋：斐波那契數(shù)字為：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】

因為斐波那契數(shù)的特點是：每一個數(shù)是前兩個數(shù)的和。所以求和項重復(fù)使用兩次時就可以由他的前后項代替，因此可以用逆序貪心求解。
先找到一個最大值不大于k的斐波那契數(shù)列；
之后借助兩個tag值逆向貪心遍歷，一個s標(biāo)記當(dāng)前遍歷的目標(biāo)和值，另一個cnt標(biāo)記當(dāng)前和的數(shù)目。
如果-當(dāng)前遍歷數(shù)仍>0，就判定該數(shù)可以作為組成和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的所有斐波那契數(shù)
        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