# 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
#
# Related Topics greedy 74 0
# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
def findMinFibonacciNumbers(self, k: int) -> int:
fib = [1, 1]
while fib[-1] < k:
fib.append(fib[-1] + fib[-2])
ret = 0
i = -1
while k > 0:
while k < fib[i]:
i -= 1
k -= fib[i]
ret += 1
return ret
# leetcode submit region end(Prohibit modification and deletion)
First, calculate whether it is less than or equal to k Fibonacci series in the range , Store it ;
Traverse from the far right with a single pointer , Each time, it is not greater than k The maximum of , from k Subtract this value from . A sequence of numbers thus chosen , And is k And the minimum quantity .
