鱼C论坛

 找回密码
 立即注册
查看: 2786|回复: 0

[技术交流] C++刷leetcode(1414. 和为 K 的最少斐波那契数字数目)【动态规划】【贪心思想】

[复制链接]
发表于 2020-6-15 14:08:29 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
题目描述:
  1. 给你数字 k ,请你返回和为 k 的斐波那契数字的最少数目,其中,每个斐波那契数字都可以被使用多次。

  2. 斐波那契数字定义为:

  3. F1 = 1
  4. F2 = 1
  5. Fn = Fn-1 + Fn-2 , 其中 n > 2 。
  6. 数据保证对于给定的 k ,一定能找到可行解。

  7.  

  8. 示例 1:

  9. 输入:k = 7
  10. 输出:2
  11. 解释:斐波那契数字为:1,1,2,3,5,8,13,……
  12. 对于 k = 7 ,我们可以得到 2 + 5 = 7 。
  13. 示例 2:

  14. 输入:k = 10
  15. 输出:2
  16. 解释:对于 k = 10 ,我们可以得到 2 + 8 = 10 。
  17. 示例 3:

  18. 输入:k = 19
  19. 输出:3
  20. 解释:对于 k = 19 ,我们可以得到 1 + 5 + 13 = 19 。
  21.  

  22. 提示:

  23. 1 <= k <= 10^9

  24. 来源:力扣(LeetCode)
  25. 链接:https://leetcode-cn.com/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k
  26. 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码


  1. class Solution {
  2. public:
  3.     int findMinFibonacciNumbers(int k) {
  4.         //使用动态规划构建斐波那契数列
  5.         vector<int> dp(2, 1);
  6.         int store = 0;
  7.         for(int i = 2; i <= k; i++){
  8.             dp.push_back(dp[i-1] + dp[i-2]);
  9.             if(dp[i] >= k)break;
  10.         }
  11.         //贪心思想
  12.         int res = 0;
  13.         int sum = k;
  14.         int j = dp.size() - 1;
  15.         while(sum != 0){
  16.             while(j > 0 && dp[j] > sum){
  17.                 j--;
  18.             }
  19.             sum -= dp[j];
  20.             res++;
  21.         }
  22.         return res;
  23.     }
  24. };
复制代码



注意事项:1.dp动态开辟空间。

本帖被以下淘专辑推荐:

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-2 14:45

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表