FibFrog.java

//doesn't pas most tests
import java.util.ArrayList;
import java.util.List;

class Solution {


    public int solution(int[] A) {

        int n = A.length; //riverLength
        if (n == 0) return 1;
        if (n == 1) return 1;
        if (n == 2) return 1;
        if (n == 3) return 1;

        List<Integer> fib = new ArrayList<>();

        fib.add(0);
        fib.add(1);

        //O(L) this should add lement #3
        for (int i = 2; i < n + 2; i++) {
            fib.add(i, fib.get(i - 1) + fib.get(i - 2));
            if (fib.get(fib.size() - 1) > n) break;
        }

        //starts from -1, needs to get to A.length
        int pos = -1; //starting
        int remainingSteps = n;
        int jumps = 0;


        while (pos <= n) {
            int hop = 0;
            for (int k = (fib.size() - 1); k > 0; k--) {
                if (fib.get(k) > remainingSteps) continue;
                if (A[fib.get(k)] == 0) continue;
                hop = fib.get(k);
                pos = pos + hop; //hop of fib[k] given
                remainingSteps = remainingSteps - hop;
                jumps++;
                break;
            }
            if (hop == 0) break;
        }

        if (jumps == 0) return -1;
        return jumps;


    }
}