Sum Of Fibonacci Numbers

How many minimum numbers from fibonacci series are required such that sum of numbers should be equal to a given Number N?
Note : repetition of number is allowed.

N = 4
Fibonacci numbers : 1 1 2 3 5 .... so on
here 2 + 2 = 4 
so minimum numbers will be 2 

Solution:

Time: O(n^n)

public class Solution {
    public int fibsum(int A) {
        List<Integer> fib = new ArrayList<>();
        fib.add(1);
        fib.add(1);
        while (fib.get(fib.size() - 1) < A) {
            fib.add(fib.get(fib.size() - 1) + fib.get(fib.size() - 2));
        }
        int min = 0;
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i : fib) queue.offer(i);
        while (!queue.isEmpty()) {
            min ++;
            int size = queue.size();
            for (int i = 0; i < size; i ++) {
                int curr = queue.poll();
                if (curr == A) return min;
                for (int val : fib) {
                    queue.offer(val + curr);
                }
            }
        }
        return min;
    }
}

Solution2:

Time: O(n)

public class Solution {
    public int fibsum(int A) {
        List<Integer> fib = new ArrayList<>();
        fib.add(1);
        fib.add(1);
        while (fib.get(fib.size() - 1) < A) {
            fib.add(fib.get(fib.size() - 1) + fib.get(fib.size() - 2));
        }
        int n = fib.size();
        // dp[i][s] = min number that sums to s for first ith element
        // dp[i][s] = min(dp[i - 1][s], dp[i][s - a[i - 1]])
        // dp[0][s] = intmax, dp[0][0] = 0
        // dp[n][s]
        int[][] dp = new int[n + 1][A + 1];
        for (int j = 1; j <= A; j ++) {
            dp[0][j] = Integer.MAX_VALUE;
        }
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= A; j ++) {
                dp[i][j] = dp[i - 1][j];
                if (j - fib.get(i - 1) >= 0 && dp[i][j - fib.get(i - 1)] != Integer.MAX_VALUE) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][j - fib.get(i - 1)] + 1);
                }
            }
        }
        // for (int[] a : dp) System.out.println(Arrays.toString(a));
        return dp[n][A];
    }
}

public class Solution {
    public int fibsum(int A) {
        List<Integer> fib = new ArrayList<>();
        fib.add(1);
        fib.add(1);
        while (fib.get(fib.size() - 1) < A) {
            fib.add(fib.get(fib.size() - 1) + fib.get(fib.size() - 2));
        }
        int n = fib.size();
        // dp[i][s] = min number that sums to s for first ith element
        // dp[i][s] = min(dp[i - 1][s], dp[i][s - a[i - 1]])
        // dp[0][s] = intmax, dp[0][0] = 0
        // dp[n][s]
        int[] dp = new int[A + 1];
        for (int j = 1; j <= A; j ++) {
            dp[j] = Integer.MAX_VALUE;
        }
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= A; j ++) {
                dp[0] = 0; 
                if (j - fib.get(i - 1) >= 0 && dp[j - fib.get(i - 1)] != Integer.MAX_VALUE) {
                    dp[j] = Math.min(dp[j], dp[j - fib.get(i - 1)] + 1);
                }
            }
        }
        // for (int[] a : dp) System.out.println(Arrays.toString(a));
        return dp[A];
    }
}

public class Solution {
    public int fibsum(int A) {
        List<Integer> fib = new ArrayList<>();
        fib.add(1);
        fib.add(1);
        while (fib.get(fib.size() - 1) < A) {
            fib.add(fib.get(fib.size() - 1) + fib.get(fib.size() - 2));
        }
        if (fib.get(fib.size() - 1) > A) fib.remove(fib.size() - 1);
        int count = 0;
        while (A > 0) {
            int index = Collections.binarySearch(fib, A);
            if (index < 0) {
                index = Math.max(- index - 2, 0);
            }
            A -= fib.get(index);
            count ++;
        }
        return count;
    }
}