【算法编程】和为 K 的最少斐波那契数字数目
给定k个数,其满足斐波那契性质,从中挑选一部分数字(每个数只能被挑选1次)使得它们的和恰巧为k。目标是求出最少能够挑选几个数满足这个条件。k取值范围为
试题来源: LeetCode.1414
难度:★★★☆☆
【输入】k=7
【输出】2
【解析】斐波那契数字为:1,1,2,3,5,8,13,……,对于 k = 7 ,我们可以得到 2 + 5 = 7 。
C++源代码:
class Solution {
public:
int findMinFibonacciNumbers(int k) {
int ans=0, i=2;
vector<int> dp(2,1);
for(i=2; i<=k; i++) {
dp.push_back(dp[i-1] + dp[i-2]);
if(dp[i] > k) break;
}
for(i=dp.size()-1; i>=0; i--){
if(k >= dp[i]){
k-=dp[i];
ans++;
}
}
return ans;
}
};
原理讲解:
(1)斐波那契数列定义为:
其中 且
,
。
(2)为了能够找到合适的解,首先我们可知数列一定是升序排列的,因此我们可以再没添加一个数时,去判断其是否比k值大,因为如果后面的数比k大,则其不可能与前面任意几个数相加等于k,所以这里可以作为一个减少额外运算的优化点;
(3)因为数列是升序排列,因为目标是尽可能找到最少的数使之和为k,因此只需要从最后一个数向前遍历,依次选择,直到满足累计的和为k即可。每一次累计时,设置一个ans变量来保存数字的数量,而此时k减去对应的值。经过分析可知,我们可以找到唯一的最优解。
知识点:
动态规划
其他解法:
class Solution {
int f[45];
public:
int findMinFibonacciNumbers(int k) {
int i,ans=0;
for(f[1]=1,i=2;i<45;i++)f[i]=f[i-1]+f[i-2];
for(i=44;i;i--)if(k>=f[i])
{
k-=f[i];
ans++;
}
return ans;
}
};