find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

Given an integer&nbsp;<code>k</code>, return the minimum number of Fibonacci numbers whose sum is equal to <code>k</code>. The same Fibonacci number can be used multiple times.

The Fibonacci numbers are defined as:

<ul>
	<li><code>F1 = 1</code></li>
	<li><code>F2 = 1</code></li>
	<li><code>Fn = Fn-1 + Fn-2</code> for <code>n &gt; 2.</code></li>
</ul>
It is guaranteed that for the given constraints we can always find such Fibonacci numbers that sum up to <code>k</code>.
&nbsp;
Example 1:

<pre>
Input: k = 7
Output: 2 
Explanation: The Fibonacci numbers are: 1, 1, 2, 3, 5, 8, 13, ... 
For k = 7 we can use 2 + 5 = 7.</pre>

Example 2:

<pre>
Input: k = 10
Output: 2 
Explanation: For k = 10 we can use 2 + 8 = 10.
</pre>

Example 3:

<pre>
Input: k = 19
Output: 3 
Explanation: For k = 19 we can use 1 + 5 + 13 = 19.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>1 &lt;= k &lt;= 109</code></li>
</ul>

findMinFibonacciNumbers

Find the Minimum Number of Fibonacci Numbers Whose Sum Is K

Greedy

Math

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

斐波那契数字定义为：

<ul>
	<li>F1 = 1</li>
	<li>F2 = 1</li>
	<li>Fn = Fn-1 + Fn-2&nbsp;， 其中 n &gt; 2 。</li>
</ul>

数据保证对于给定的 <code>k</code>&nbsp;，一定能找到可行解。

&nbsp;

示例 1：

<pre>输入：k = 7
输出：2 
解释：斐波那契数字为：1，1，2，3，5，8，13，&hellip;&hellip;
对于 k = 7 ，我们可以得到 2 + 5 = 7 。</pre>

示例 2：

<pre>输入：k = 10
输出：2 
解释：对于 k = 10 ，我们可以得到 2 + 8 = 10 。
</pre>

示例 3：

<pre>输入：k = 19
输出：3 
解释：对于 k = 19 ，我们可以得到 1 + 5 + 13 = 19 。
</pre>

&nbsp;

提示：

<ul>
	<li><code>1 &lt;= k &lt;= 10^9</code></li>
</ul>