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) - 1
while k:
if k >= f[i]:
k -= f[i]
ans += 1
i -= 1
return ans