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

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

解题

这题解题的时候，首先要先明白什么是斐波那契数字:斐波那契数列这里就放个连接大家自己去看看吧，毕竟这就是算法不是特别研究的数学。

那么如何求导斐波那契数字就成了关键，根据斐波那契数字定义为：

F1 = 1 F2 = 1 Fn = Fn-1 + Fn-2 ， 其中 n > 2 。

我们可以总结出下面的规律：

• F1 = 1
• F2 = 1
• F3 = F2 + F1 => 2
• F4 = F3 + F2 => 3
• F5 = F4 + F3 => 5
• F6 = F5 + F4 => 8
• F7 = F6 + F5 => 13
• F8 = F7 + F6 => 21
• F9 = F8 + F7 => 34

根据规律我们可以很容易的求导出这样的函数：

 function progrom(n) {
  switch(n) {
    case 1:
    case 2:
      console.log('第（0）项目：1'.n)
    default: 
      let fn_1 = 1, fn_2 = 1, fn
      // 第一项和第二项我们已经走掉了，所以从3开始
      for(let i = 3; i<=n; i++) {
        // Fn = Fn-1 + Fn-2 ， 其中 n > 2 。
        fn = fn_2 + fn_1
        console.log(`第${i}项：`, fn)
        // 每次计算完毕 第n项后，我们需要将 前两项前移
        fn_1 = fn_2
        fn_2 = fn
      }
      break
  }
};

当我们需要获得的第几个斐波那契数列的，不是 F1、F2的时候，我们就需要进行循环添加的操作

Q：这几个变量的定义是为什么？

let fn_1 = 1, fn_2 = 1, fn

A：双指针，每次赋值完毕之后都向前进行移动

正式解题

有了上面的解题思路之后，我们就可以正式来看这题了。

我的思路是：

1. 利用上面的公式，求出当前大于or等于数字 k的斐波那契数字，并且使用数组进行存储之前小于数字 k的斐波那契数字
2. 然后我们就可以进行循环我们得出的数，然后：

• if(数组[index] < 数字 k 的时候) => 结果值+1; 数字 k -= 数组[index]
• if(数组[index] > 数字 k 的时候) => 不处理
• if(数组[index] === 数字 k 的时候) => 结果值+1; 数字 k = 0
• 最后 返回结果值+ k*1(每个斐波那契数字都可以被使用多次。)

我们就默认都使用1

/**
 * @param {number} k
 * @return {number}
 */
function findMinFibonacciNumbers(k) {
  let fn_1 = 1, fn_2 = 1, fn = 0
  let n = 1
  let res = []
  while (fn < k) {
    switch(n) {
      case 1:
      case 2:
        fn = 1
        res.push(fn)
        break
      default: 
        // 第一项和第二项我们已经走掉了，所以从3开始
        // for(let i = 3; i<=n; i++) {
          // Fn = Fn-1 + Fn-2 ， 其中 n > 2 。
          fn = fn_2 + fn_1
          res.push(fn)
          // 每次计算完毕 第n项后，我们需要将 前两项前移
          fn_2 = fn_1
          fn_1 = fn
        // }
        break
    }
    n++
  }
  let count = 0
  for(let i = res.length -1; i >= 0; i--) {
    if(res[i] === k) {
      k = 0
      count ++
      break
    } else if (res[i] <= k){
      k = k -res[i]
      count ++
    }
  }
  return count + k*1
};

希望有可以优化的小伙伴，来一起探讨一下！