Simulation volume leetcode [general] 1414 The minimum number of Fibonacci numbers with a sum of K

Summary ： Simulation volume Leetcode Summary of questions

1414. And for K The minimum number of Fibonacci Numbers

Here are the numbers k , Please return and for  k  The minimum number of Fibonacci numbers , among , Each Fibonacci number can be used many times .

Fibonacci numbers are defined as ：

F1 = 1
F2 = 1
Fn = Fn-1 + Fn-2 , among n > 2 .
Data guarantee for a given k , A feasible solution must be found .

Example 1：

Input ：k = 7
Output ：2
explain ： Fibonacci number is ：1,1,2,3,5,8,13,……
about k = 7 , We can get 2 + 5 = 7 .
Example 2：

Input ：k = 10
Output ：2
explain ： about k = 10 , We can get 2 + 8 = 10 .
Example 3：

Input ：k = 19
Output ：3
explain ： about k = 19 , We can get 1 + 5 + 13 = 19 .

Tips ：

1 <= k <= 10^9

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Code ：

from leetcode_python.utils import *


class Solution:
    def findMinFibonacciNumbers(self, k: int) -> int:
        f = [1,1]
        while f[-1]<k:f.append(f[-1]+f[-2])
        res,i = 0,len(f)-1
        while k:
            if k>=f[i]:
                k-=f[i]
                res+=1
            i-=1
        return res


def test(data_test):
    s = Solution()
    data = data_test  # normal
    # data = [list2node(data_test[0])] # list turn node
    return s.getResult(*data)


def test_obj(data_test):
    result = [None]
    obj = Solution(*data_test[1][0])
    for fun, data in zip(data_test[0][1::], data_test[1][1::]):
        if data:
            res = obj.__getattribute__(fun)(*data)
        else:
            res = obj.__getattribute__(fun)()
        result.append(res)
    return result


if __name__ == '__main__':
    datas = [
        [],
    ]
    for data_test in datas:
        t0 = time.time()
        print('-' * 50)
        print('input:', data_test)
        print('output:', test(data_test))
        print(f'use time:{
      time.time() - t0}s')

remarks ：
GitHub：https://github.com/monijuan/leetcode_python

CSDN Summary ： Simulation volume Leetcode Summary of questions

You can add QQ Group communication ：1092754609

leetcode_python.utils See the description on the summary page for details
First brush questions , Then generated by script blog, If there is any mistake, please leave a message , I see it will be revised ！ thank you ！