class Solution {
public:
int findMinFibonacciNumbers(int k) {
}
};
1414. 和为 K 的最少斐波那契数字数目
给你数字 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原站题解
golang 解法, 执行用时: 0 ms, 内存消耗: 2.4 MB, 提交时间: 2022-11-20 17:06:22
func findMinFibonacciNumbers(k int) (ans int) {f := []int{1, 1}for f[len(f)-1] < k {f = append(f, f[len(f)-1]+f[len(f)-2])}for i := len(f) - 1; k > 0; i-- {if k >= f[i] {k -= f[i]ans++}}return}
python3 解法, 执行用时: 48 ms, 内存消耗: 14.8 MB, 提交时间: 2022-11-20 17:05:51
class Solution:def findMinFibonacciNumbers(self, k: int) -> int:f = [1, 1]while f[-1] < k:f.append(f[-1] + f[-2])ans, i = 0, len(f) - 1while k:if k >= f[i]:k -= f[i]ans += 1i -= 1return ans