Leetcode 1414:和为K的最少斐波那契数字数目(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1414:和为K的最少斐波那契数字数目(超详细的解法!!!)

in leetcode with 0 comment

给你数字 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 。

提示:

解题思路

首先不难想到暴力解法,每次选择比k小的最近的那个斐波那契数(通过二分法),然后统计使用了多少个斐波那契数即可。

class Solution:
    def findMinFibonacciNumbers(self, k: int) -> int:
        data = []
        def fab():
            a, n, b = 0 , 0, 1
            while b <= k:
                data.append(b)
                a, b = b, a + b
        fab()
        res = 0
        while k:
            i = bisect.bisect(data, k)
            res += k // data[i - 1]
            k %= data[i - 1]
        return res

我们可以将空间复杂度降到O(1),先算出离k最近的两个斐波那契数(其中一个大于k,另外一个小于k),然后往下递减,也就是

class Solution:
    def findMinFibonacciNumbers(self, k: int) -> int:
        res, a, b = 0, 1, 1
        while b <= k:
            a, b = b, a + b

        while a:
            while a <= k:
                k -= a
                res += 1
            a, b = b - a, a
        return res

其实我们可以发现每个斐波那契数只会使用一次,为什么呢?

$f(k+1)-f(k)=(f(k)+f(k-1))-(f(k-1)+f(k-2))$

$f(k+1)-f(k)=f(k)-f(k-2)$

$2*f(k)=f(k+1)+f(k-2)$

也就是说如果有两个相同的斐波那契数,那么可以转化为两个不同的斐波那契数。

那么上面代码中的while可以修改成if

class Solution:
    def findMinFibonacciNumbers(self, k: int) -> int:
        res, a, b = 0, 1, 1
        while b <= k:
            a, b = b, a + b

        while a:
            if a <= k: # 修改
                k -= a
                res += 1
            a, b = b - a, a
        return res

reference:

https://leetcode.com/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k/discuss/585632/JavaC%2B%2BPython-Easy-Prove

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses