Find minimum number of fibonacci numbers whose sum is equal to given number K

问题

fib数相加和等于K的最少fib数个数有多少。

答案

贪心做法，每次取<=K的最大的fib数，递归下去。

证明

https://codeforces.com/blog/entry/60305 两种证明方法

• 第一种：这些fib数中最大的那个数不能出现两次，采用反证法，如果超过3次及以上，由f(i) = f(i-1) + f(i-2) | f(i-1) + f(i) = f(i+1) | f(i) + f(i+1) = f(i+2)三个等式相加得到3*f(i) = f(i-2) + f(i + 2)，这样个数是减少的，所以不可能。如果等于2次，假设有f(i+1)，那么f(i+1) + f(i) = f(i+2)，不是最优的，肯定不对，假设没有f(i+1)，根据f(i) = f(i-1) + f(i-2) | f(i) + f(i-1) = f(i+1)得到2*f(i) = f(i-1) + f(i-2)，这样来看，其实最大的数是可以只有一次的，而且数没有变多。根据最大的数只有一次，不停递归，我们可以证明，对于K只有一种表示方法没有重复的数字，且是最优的。PS：对于这个证明，我觉得还需要提一下f(i) + 任意一个f(k) > f(i - 1) + 任意一个f(l)，当然，这个是很显然地，f(i - 1) + f(l)是<= f(i)的，而f(k) >= 1。这样我们才能说，每次都要取最大的那个数，因为最大的那个数不能被其他的形式替换。
• 第二种：我们对这个要求序列用01表达，然后根据上面可以证明这个表达不会超过1，显然也不会有连续的1，如果不能有连续的1话，对于比k小的最大的f(i)来说，如果不选第i个数，无论怎么选，加和都小于f(i)，因为1 + (f(1) + f(3) + ... + f(2k - 1)) = f(2k), 1 + (f(2) + f(4) + ... + f(2k)) = f(2k + 1)。所以必须每次选择最大的那个！