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]; }