力扣 1414. 和为 K 的最少斐波那契数字数目

三更鬼

于 2022-02-03 23:30:45 发布

阅读量334

点赞数

分类专栏：贪心文章标签： leetcode 动态规划算法

本文链接：https://blog.csdn.net/csdn_muxin/article/details/122780033

版权

贪心专栏收录该内容

19 篇文章

订阅专栏

本文介绍了解决LeetCode问题的方法，通过计算斐波那契数列找出构成整数k所需的最少元素数量。关键在于每次选择最大不超过k的斐波那契数，直至k为0。代码实现展示了如何遍历并计数这些数列元素。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目来源：https://leetcode-cn.com/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k/

大致题意：
给一个整数 k，求出最少使用多少个斐波那契数列的元素可以组成 k

思路

若想使用最少的元素组成，那么每次选用的数列元素就应该是满足要求的最大元素

于是可以每次将当前数 k 减去不大于 k 的最大的斐波那契数列元素

代码：

public int findMinFibonacciNumbers(int k) {
        int[] f = new int[100];
        int len = 2;
        f[0] = 0;
        f[1] = 1;
        f[2] = 1;
        // 计算出不大于 k 的斐波那契数列
        while (f[len] <= k) {
            len++;
            f[len] = f[len - 1] + f[len - 2];
        }
        int ans = 0;
        // 求出需要的数列元素个数
        while (k != 0 && len > 0) {
            if (k >= f[len]) {
                k -= f[len];
                ans++;
            }
            len--;
        }
        return ans;
    }