难度: Medium
给你数字 k ，请你返回和为 k 的斐波那契数字的最少数目，其中，每个斐波那契数字都可以被使用多次。
斐波那契数字定义为：
数据保证对于给定的 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运行时间: 24 ms
内存: 0.0 MB
class Solution:
def findMinFibonacciNumbers(self, k: int) -> int:
if k < 2: return k
a = b = 1
while b <= k:
a, b = b, a + b
return self.findMinFibonacciNumbers(k - a) + 1
这个题解采用了递归方法来找到和为 k 的最少斐波那契数字数目。首先，生成小于或等于 k 的斐波那契数列，然后从最大的斐波那契数开始尝试。如果当前斐波那契数小于或等于 k，则将 k 减去这个数，并对新的 k 递归求解，同时计数增加1。这个过程一直持续，直到 k 为0，即找到了和为原始 k 的斐波那契数的组合。递归的深度即为所需的最少斐波那契数目。
时间复杂度: O(log(k))
空间复杂度: O(log(k))
class Solution:
def findMinFibonacciNumbers(self, k: int) -> int:
if k < 2: return k # 如果 k 小于 2，则直接返回 k
a = b = 1 # 初始化斐波那契数列的前两个数
while b <= k: # 生成小于等于 k 的斐波那契数列
a, b = b, a + b # 更新斐波那契数
# 递归调用，k 减去最近的较大斐波那契数，计数加1
return self.findMinFibonacciNumbers(k - a) + 1
在生成斐波那契数列的过程中，使用`while b <= k`确保b是不超过k的最大斐波那契数。如果使用`while a + b <= k`，则在循环结束时，b的值已经是超过k的第一个斐波那契数，而我们需要的是不超过k的最大斐波那契数。使用`while b <= k`可以直接确保b是符合条件的最大值，用于后续递归减法操作。因此，这样操作不会导致最后一个数超过k，而是确保了最后一个数是小于等于k的最大斐波那契数。
在这个递归解法中，每次递归调用都会将k减去当前不超过k的最大斐波那契数b。由于b是小于或等于k的最大斐波那契数，所以每次递归调用必然会使k减少，并且减少的量至少为1（当k为1时）。通过这种方式，k的值会在每次递归中逐步减小，直到最终降至0，从而避免了无限递归的问题。
在斐波那契数列中，最初的两个数字是1和1。当k小于2（即k为0或1）时，直接返回k是因为k本身就与斐波那契数列中的数对应。具体来说，当k为0时，需要0个斐波那契数来表示，而当k为1时，需要1个斐波那契数（即1）来表示。这种处理方式简化了问题的解法，因为针对这些小值，解决方案是直观且明显的。