C++刷leetcode（1414. 和为 K 的最少斐波那契数字数目）【动态规划】【贪心思想】

糖逗

题目描述:

1. 给你数字 k ，请你返回和为 k 的斐波那契数字的最少数目，其中，每个斐波那契数字都可以被使用多次。
   
2. 
   
3. 斐波那契数字定义为：
   
4. 
   
5. F1 = 1
   
6. F2 = 1
   
7. Fn = Fn-1 + Fn-2 ， 其中 n > 2 。
   
8. 数据保证对于给定的 k ，一定能找到可行解。
   
9. 
   
10.  
    
11. 
    
12. 示例 1：
    
13. 
    
14. 输入：k = 7
    
15. 输出：2
    
16. 解释：斐波那契数字为：1，1，2，3，5，8，13，……
    
17. 对于 k = 7 ，我们可以得到 2 + 5 = 7 。
    
18. 示例 2：
    
19. 
    
20. 输入：k = 10
    
21. 输出：2
    
22. 解释：对于 k = 10 ，我们可以得到 2 + 8 = 10 。
    
23. 示例 3：
    
24. 
    
25. 输入：k = 19
    
26. 输出：3
    
27. 解释：对于 k = 19 ，我们可以得到 1 + 5 + 13 = 19 。
    
28.  
    
29. 
    
30. 提示：
    
31. 
    
32. 1 <= k <= 10^9
    
33. 
    
34. 来源：力扣（LeetCode）
    
35. 链接：https://leetcode-cn.com/problems/find-the-minimum-number-of-fibonacci-numbers-whose-sum-is-k
    
36. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

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动态开辟空间。