Question

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

English Version

题目描述

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

解法

方法一

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)

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);
  }
}

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);
  }
};

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)
}

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;
}

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
  }
}