https://codility.com/programmers/lessons/13-fibonacci_numbers/fib_frog/

Explanation: Coming soon

// you can use includes, for example:
// #include <algorithm>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

#define DEBUG 0

#if DEBUG
#   define LOG(...) printf(__VA_ARGS__)
#else
#   define LOG(...)
#endif

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    int max_dist = A.size() + 1;
    vector<int> fibs;//fibonacci numbers in range [1 - A.size()];
    fibs.reserve(max_dist);
    fibs.push_back(0);//f(0)
    fibs.push_back(1);//f(1)
    int k = 1;
    while (fibs[k++] < max_dist)
    {
        fibs.push_back(fibs[k - 1] + fibs[k - 2]);
    }

    #if DEBUG
    LOG("fibs=");
    for (auto & fib: fibs)
    {
        LOG("%d ", fib);
    }
    LOG("\n");
    #endif

    //now calculate min jumps from starting pont & every leaf to the bank, starting from right most leaf
    //starting point is at 0 index
    int total_points = max_dist;
    vector<int> min_jumps(total_points);
    fill(min_jumps.begin(), min_jumps.end(), -1);
    k = total_points - 1;

    LOG("first k = %d\n", k);

    //O(N) loops
    while(k > -1)
    {
        if (k > 0 && A[k - 1] == 0)//no leaf
        {
            k--;
            continue;
        }

        //now try every possible jump starting from largest one.O(logN) complexity
        for (int jump_idx = fibs.size() - 1; jump_idx > 0; --jump_idx)
        {
            bool valid_jump = false;
            int jump_dist = fibs[jump_idx];
            int destination = k + jump_dist;

            LOG("Try from %d to %d by %d (f(%d)) jump\n", k - 1, destination - 1, jump_dist, jump_idx);

            if (destination > total_points || (destination < total_points && A[destination - 1] == 0))//invalid landing point
                continue;

            int current_jumps = 1;
            if (destination == total_points)//landing on the river bank in one jump
            {
                valid_jump = true;
            }
            else //landing on a leaf
            {
                if (min_jumps[destination] != -1)//if there is a valid way from this leaf to the river bank
                {
                    LOG("-> from destination (%d) to river bank min_jumps[%d]=%d\n", destination - 1, destination, min_jumps[destination]);
                    current_jumps += min_jumps[destination];
                    valid_jump = true;
                }
            }

            if (valid_jump && (min_jumps[k] == -1 || min_jumps[k] > current_jumps))
            {
                min_jumps[k] = current_jumps;

                LOG("Updated min jumps from %d (min_jumps[%d]) = %d\n", k - 1, k, min_jumps[k]);
            }
        }

        k--; //next leaf on the left
    }

    return min_jumps[0];
}