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

题目描述

给你数字 k ，请你返回和为 k 的斐波那契数字的最少数目，其中，每个斐波那契数字都可以被使用多次。

斐波那契数字定义为：

F₁ = 1
F₂ = 1
F_n = F_n-1 + F_n-2 ，其中 n > 2 。

数据保证对于给定的 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

解法

方法一：贪心

我们可以每次贪心地选取一个不超过 \(k\) 的最大的斐波那契数，然后将 \(k\) 减去该数，答案加一，一直循环，直到 \(k = 0\) 为止。

由于每次贪心地选取了最大的不超过 \(k\) 的斐波那契数，假设为 \(b\)，前一个数为 \(a\)，后一个数为 \(c\)。将 \(k\) 减去 \(b\)，得到的结果，一定小于 \(a\)，也即意味着，我们选取了 \(b\) 之后，一定不会选到 \(a\)。这是因为，如果能选上 \(a\)，那么我们在前面就可以贪心地选上 \(b\) 的下一个斐波那契数 \(c\)，这不符合我们的假设。因此，我们在选取 \(b\) 之后，可以贪心地减小斐波那契数。

时间复杂度 \(O(\log k)\)，空间复杂度 \(O(1)\)。

Python3JavaC++GoTypeScriptRust

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

class Solution {
    public int findMinFibonacciNumbers(int k) {
        int a = 1, b = 1;
        while (b <= k) {
            int c = a + b;
            a = b;
            b = c;
        }
        int ans = 0;
        while (k > 0) {
            if (k >= b) {
                k -= b;
                ++ans;
            }
            int c = b - a;
            b = a;
            a = c;
        }
        return ans;
    }
}

class Solution {
public:
    int findMinFibonacciNumbers(int k) {
        int a = 1, b = 1;
        while (b <= k) {
            int c = a + b;
            a = b;
            b = c;
        }
        int ans = 0;
        while (k > 0) {
            if (k >= b) {
                k -= b;
                ++ans;
            }
            int c = b - a;
            b = a;
            a = c;
        }
        return ans;
    }
};

func findMinFibonacciNumbers(k int) (ans int) {
    a, b := 1, 1
    for b <= k {
        c := a + b
        a = b
        b = c
    }

    for k > 0 {
        if k >= b {
            k -= b
            ans++
        }
        c := b - a
        b = a
        a = c
    }
    return
}

function findMinFibonacciNumbers(k: number): number {
    let [a, b] = [1, 1];
    while (b <= k) {
        let c = a + b;
        a = b;
        b = c;
    }

    let ans = 0;
    while (k > 0) {
        if (k >= b) {
            k -= b;
            ans++;
        }
        let c = b - a;
        b = a;
        a = c;
    }
    return ans;
}

impl Solution {
    pub fn find_min_fibonacci_numbers(mut k: i32) -> i32 {
        let mut a = 1;
        let mut b = 1;
        while b <= k {
            let c = a + b;
            a = b;
            b = c;
        }

        let mut ans = 0;
        while k > 0 {
            if k >= b {
                k -= b;
                ans += 1;
            }
            let c = b - a;
            b = a;
            a = c;
        }
        ans
    }
}

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

题目描述

解法

方法一：贪心

评论