1414. Find the Minimum Number of Fibonacci Numbers Whose Sum Is K-和为 K 的最少斐波那契数字数目

给你数字k，请你返回和为k的斐波那契数字的最少数目，其中，每个斐波那契数字都可以被使用多次。

斐波那契数字定义为：

• F_1 = 1
• F_2 = 1
• F_n = F_{n-1} + F_{n-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

1.深度搜索
Python:

class Solution:
    def findMinFibonacciNumbers(self, k: int) -> int:
        lis = [1]
        f1, f2 = 1, 1
        while lis[-1] < k:
            fn = f1 + f2
            if fn <= k:
                lis.append(fn)
                f1, f2 = f2, fn
            else:
                break
        result = 0
        def backtrace(lis, temp, n):
            nonlocal result
            if temp < 0 or result != 0:
                return 
            elif temp == 0:
                result = n
                return 
            for item in lis[::-1]:
                backtrace(lis, temp-item, n+1)
        backtrace(lis, k, 0)
        return result

Java:

class Solution {
    public int findMinFibonacciNumbers(int k) {
        List<Integer> flist = new ArrayList<>();
        flist.add(1);
        int f1 = 1;
        int f2 = 1;
        int fn;
        while(flist.get(flist.size()-1) < k)
        {
            fn = f1 + f2;
            if(fn <= k)
            {
                flist.add(fn);
                f1 = f2;
                f2 = fn;
            }
            else
                break;
        }
        int[] lis = new int[flist.size()];
        for(int i = 0; i < lis.length; i++)
        {
            lis[i] = flist.get(lis.length-i-1);
        }
        return backtrace(lis, k, 0);
    }

    public int backtrace(int[] list, int temp, int n)
    {
        if(temp < 0)
            return 0;
        else if(temp == 0)
        {
            return n;
        }
        int result;
        for(int a: list)
        {
            result = backtrace(list, temp-a, n+1);
            if(result != 0)
                return result;
        }
        return 0;
    }
}

2.贪心算法
Python:

class Solution:
    def findMinFibonacciNumbers(self, k: int) -> int:
        lis = [1]
        f1, f2 = 1, 1
        while lis[-1] < k:
            fn = f1 + f2
            if fn <= k:
                lis.append(fn)
                f1, f2 = f2, fn
            else:
                break
        i = len(lis)-1
        total = 0
        while k > 0:
            k -= lis[i]
            i -= 1
            total += 1
            if k == 0:
                return total
            else:
                while k < lis[i]:
                    i -= 1
        return total

Java:

class Solution {
    public int findMinFibonacciNumbers(int k) {
        List<Integer> flist = new ArrayList<>();
        flist.add(1);
        int f1 = 1;
        int f2 = 1;
        int fn;
        while(flist.get(flist.size()-1) < k)
        {
            fn = f1 + f2;
            if(fn <= k)
            {
                flist.add(fn);
                f1 = f2;
                f2 = fn;
            }
            else
                break;
        }
        int[] lis = new int[flist.size()];
        for(int i = 0; i < lis.length; i++)
        {
            lis[i] = flist.get(lis.length-i-1);
        }
        int j = 0;
        int total = 0;
        while(k > 0)
        {
            k -= lis[j];
            total += 1;
            j += 1;
            if(k == 0)
                return total;
            else
            {
                while(k < lis[j])
                    j ++;
            }
        }
        return total;
    }

}