“This is the 20th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

The title

Given the number k, return the minimum number of Fibonacci numbers that sum to k, where each Fibonacci number can be used multiple times. Fibonacci numbers are defined as: F1 = 1 F2 = 1 Fn = FN-1 + Fn-2, where n > 2. The data guarantees that for a given k, a feasible solution can be found.

Example 1: Input: k = 7 Output: 2 Explanation: The Fibonacci numbers are: 1, 1, 2, 3, 5, 8, 13… For k = 7, we get 2 plus 5 is equal to 7.

Example 2: Input: k = 10 Output: 2 Explanation: For k = 10, we get 2 + 8 = 10.

Example 3: Input: k = 19 Output: 0 Explanation: For k = 19, we get 1 + 5 + 13 = 19.

Train of thought

The first thought was to use the full backpack, after looking at the solution, found greedy method, code introduction, very clever proof. In addition, the official problem solving and proving process is somewhat complicated, and it takes a certain amount of time to understand the logical relationship, so let’s summarize again. The possible key point of the greedy method is that there must be an optimal solution that contains the largest Fibonacci number f[m] not exceeding K. First of all, if the above conclusion is true, then the greedy algorithm is very simple, since it must contain f[m], then it can be converted to solving k-f[m], which is a subproblem of the original problem, and so on until k=0. Now, let’s see how we can prove this. Before we prove this directly, let’s look at two sub-conclusions:

  1. The optimal solution must not contain two consecutive Fibonacci numbers
  2. There is an optimal solution that does not contain duplicates

The proof of conclusion 1 is relatively simple, and can be used anyway. Assuming that the optimal solution contains two consecutive terms, denoted as f[k] and F [k+1], according to Fibonacci theorem, we know that F [k+2] = F [k] + f[k+1], so f[k+2] is used to replace F [k] and f[k+1]. If you subtract 1 term from the sum, it’s obviously better than the original solution, so the hypothesis doesn’t work. Conclusion 2, we can deduce as follows: suppose there is an optimal solution with repeated terms, denoted as 2f[k].

2f[k] = f[k] + f[k] = (f[k+1]-f[k-1]) + (f[k-1]+f[k-2]) = f[k+1] + f[k-2]

That is, two different terms f[k+1] and f[k-2] can be used to replace the repeated 2f[k], so conclusion 2 is valid. Next, according to the above two sub-conclusions, we will clearly prove our final conclusion that there must be an optimal solution including F [m]. Here, one point of the official solution is not completely broken: This set contains no consecutive terms and no optimal solution for repeated terms. If it does not contain the largest Fibonacci number f[m] not exceeding K, then the remaining numbers, even if selected all, will not make up k. According to the above two sub-conclusions, we can divide m into two cases according to the parity of m to calculate the remaining maximum sum except f[m] :

  1. M is odd, sum = f[m-1] + f[m-3] +… + f[4] + f[2] = f[m-1] + f[m-3] +… + f[4] + f[2] + f[1] – f[1] = f[m] – 1
  2. M is even, sum = f[m-1] + f[m-3] +… + f[3] + f[1] = f[m-1] + f[m-3] +… + f[3] + f[2] = f[m]

And you can see, in either case, you can get it

sum <= f[m] < k

Therefore, if f[m] is not selected at this time, the remaining k is insufficient even if all is selected, so f[m] must be selected. In summary, the original conclusion that “there must be a set of optimal solutions containing the maximum Fibonacci number f[m] not exceeding K” is proved to be valid.

Java version code

class Solution { public int findMinFibonacciNumbers(int k) { List<Integer> fabList = new ArrayList<>(); fabList.add(1); fabList.add(1); int index = 1; while (fabList.get(index) < k) { index++; fabList.add(fabList.get(index-2) + fabList.get(index-1)); } int ans = 0; for (int i = index; i >= 0; i--) { if (k >= fabList.get(i)) { ans++; k -= fabList.get(i); } } return ans; }}Copy the code