↓Skip to main content
  1. Posts/

LeetCode-1414 和为 K 的最少斐波那契数字数目

·1 min·
Table of Contents

LeetCode-1414 和为 K 的最少斐波那契数字数目 #

Solution 1 #

贪心, 每次选不超过当前剩余数的最大斐波那契数即可. 详细的证明可以参考官方题解 和为 K 的最少斐波那契数字数目 . 代码如下:

class Solution {
public:
    #define ll long long
    ll F[100] = {0};
    ll f(int i) {
        if (F[i] != 0) {
            return F[i];
        }
        if (i == 1 || i == 2) {
            F[i] = 1;
            return 1;
        }
        F[i] = f(i - 1) + f(i - 2);
        return F[i];
    }
    int findMinFibonacciNumbers(int k) {
        int ans = 0;
        while (k != 0) {
            int l = 0;
            int r = 100;
            while (l < r) {
                int m = l + (r - l) / 2;
                if (f(m) <= k) {
                    l = m + 1;
                }
                else {
                    r = m;
                }
            }
            ans++;
            k -= f(l - 1);
        }
        return ans;
    }
};