Description

Submission

class Solution {
public:
    int findMinFibonacciNumbers(int k) {
        vector<int> fib {1, 1};

        for(int i = 2; fib.back() < k; ++i) {
            fib.push_back(fib[i-1] + fib[i-2]);
        } 

        int ret = 0;
        for(int i = fib.size() - 1; i >= 0; --i) {
            int x = fib[i];
            int t = k / x;
            
            ret += t;
            k -= t * x;
            if(k == 0) break;
        }

        return ret;
    }
};