Skip to content

Latest commit

 

History

History
198 lines (155 loc) · 4.37 KB

README.md

File metadata and controls

198 lines (155 loc) · 4.37 KB
Raw
comments difficulty edit_url rating source tags
true
中等
1465
第 24 场双周赛 Q2
贪心
数学

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

English Version

题目描述

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

斐波那契数字定义为：

  • F1 = 1
  • F2 = 1
  • Fn = Fn-1 + Fn-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

解法

方法一

Python3

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

        return dfs(k)

Java

class Solution {

    public int findMinFibonacciNumbers(int k) {
        if (k < 2) {
            return k;
        }
        int a = 1, b = 1;
        while (b <= k) {
            b = a + b;
            a = b - a;
        }
        return 1 + findMinFibonacciNumbers(k - a);
    }
}

C++

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

Go

func findMinFibonacciNumbers(k int) int {
	if k < 2 {
		return k
	}
	a, b := 1, 1
	for b <= k {
		a, b = b, a+b
	}
	return 1 + findMinFibonacciNumbers(k-a)
}

TypeScript

const arr = [
    1836311903, 1134903170, 701408733, 433494437, 267914296, 165580141, 102334155, 63245986,
    39088169, 24157817, 14930352, 9227465, 5702887, 3524578, 2178309, 1346269, 832040, 514229,
    317811, 196418, 121393, 75025, 46368, 28657, 17711, 10946, 6765, 4181, 2584, 1597, 987, 610,
    377, 233, 144, 89, 55, 34, 21, 13, 8, 5, 3, 2, 1,
];

function findMinFibonacciNumbers(k: number): number {
    let res = 0;
    for (const num of arr) {
        if (k >= num) {
            k -= num;
            res++;
            if (k === 0) {
                break;
            }
        }
    }
    return res;
}

Rust

const FIB: [i32; 45] = [
    1836311903, 1134903170, 701408733, 433494437, 267914296, 165580141, 102334155, 63245986,
    39088169, 24157817, 14930352, 9227465, 5702887, 3524578, 2178309, 1346269, 832040, 514229,
    317811, 196418, 121393, 75025, 46368, 28657, 17711, 10946, 6765, 4181, 2584, 1597, 987, 610,
    377, 233, 144, 89, 55, 34, 21, 13, 8, 5, 3, 2, 1,
];

impl Solution {
    pub fn find_min_fibonacci_numbers(mut k: i32) -> i32 {
        let mut res = 0;
        for &i in FIB.into_iter() {
            if k >= i {
                k -= i;
                res += 1;
                if k == 0 {
                    break;
                }
            }
        }
        res
    }
}