|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
题目描述:
- 给你数字 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 。
-  
- 提示:
- 1 <= k <= 10^9
- 来源:力扣(LeetCode)
- 链接:https://leetcode-cn.com/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k
- 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码
- class Solution {
- public:
- int findMinFibonacciNumbers(int k) {
- //使用动态规划构建斐波那契数列
- vector<int> dp(2, 1);
- int store = 0;
- for(int i = 2; i <= k; i++){
- dp.push_back(dp[i-1] + dp[i-2]);
- if(dp[i] >= k)break;
- }
- //贪心思想
- int res = 0;
- int sum = k;
- int j = dp.size() - 1;
- while(sum != 0){
- while(j > 0 && dp[j] > sum){
- j--;
- }
- sum -= dp[j];
- res++;
- }
- return res;
- }
- };
复制代码
注意事项:1.dp动态开辟空间。 |
|