1414. Find the Minimum Number of Fibonacci Numbers Whose Sum Is K

https://leetcode.com/contest/biweekly-contest-24/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k/

这一题，乍一看跟Fibonacci相关，很让人摸不着头脑。因为你无法确定一个数是否可以任由fibonacci数组成。可是事实上，当我们得知这就是一道coin change的题时，我知道从最大fib数开始，采用greedy 方式，就能得到minimum 解。Code 很直白

class Solution:
    def getFib(self,k):
        arr = [1,1]
        while True:
            n = arr[-1] + arr[-2]
            if n > k:
                return arr
            arr.append(n)
        return [-1]
    
    def findMinFibonacciNumbers(self, k: int) -> int:
        fibs = self.getFib(k)
        i = len(fibs)-1
        cnt = 0
        while k > 0:
            cnt += k // fibs[i]
            k = k % fibs[i]
            i-=1
        return cnt
        

下面是GeeksforGeeks的解法：

https://www.geeksforgeeks.org/minimum-fibonacci-terms-sum-equal-k/