# L13-Fibonaccinumbers
###### tags: `Codility_lessons`
## Question
https://app.codility.com/programmers/lessons/13-fibonacci_numbers/fib_frog/
## Key
青蛙只能跳費氏數列長度，且目標的位置要有樹葉才能跳，所以先將河寬大小的費氏數列存起來，接著逐一確認是否數列大小的位置有樹葉，如果有就紀錄移動後的位置，如果沒有就繼續遍尋，都沒有的話，代表跳不過去
## Reference
## Solution
### SOL.1 (with BUG, score = 75%)

#include <set>
vector<int> getJumps(int max)
{
    if (max == 0)
        return vector<int>(1, 0);
    vector<int> fib(2, 0);
    fib[1] = 1;
    for(int i = 0; fib[fib.size()-1] + fib[fib.size() - 2] < max ; i++)
    {
        fib.push_back(fib[fib.size()-1] + fib[fib.size() - 2]);
    }
    return fib;
}

int solution(vector<int> &A) {
    // write your code in C++14 (g++ 6.2.0)
    int N = A.size();
    vector<int> fib = getJumps(N);
    set<int> positions;
    positions.insert(A.size());

    for(int jumps = 1; ; jumps++)
    {
        set<int> new_positions;
        for(int pos:positions)
        {
            for(int f:fib)
            {
                // return jumps if we reach to the start point
                if (pos - (f - 1) == 0)
                    return jumps;
                
                int pre_pos = pos - f;
                
                // we do not need to calculate bigger jumps.
                if (pre_pos < 0)
                    break;
                if(pre_pos < A.size() && A[pre_pos])
                {
                    new_positions.insert(pre_pos);
                }

            }
        }

        positions = new_positions;
        if (new_positions.size() == 0)
        {
            return -1;
        }
            
    }
    return -1;

}

### SOL. II (Correct)

vector<int> getFibonacciArrayMax(int MaxNum) {
    if (MaxNum == 0)
        return vector<int>(1, 0);
    vector<int> fib(2, 0);
    fib[1] = 1;
    for (int i = 2; fib[fib.size()-1] + fib[fib.size() - 2] <= MaxNum; i++)
        fib.push_back(fib[i - 1] + fib[i - 2]);
    return fib;
}

int solution1(vector<int>& A) {
    int N = A.size();
    if (N == 0)
        return 1;
    A.push_back(1);
    N++;
    vector<int> f = getFibonacciArrayMax(N);
    const int oo = 1'000'000;
    vector<int> moves(N, oo);
    
    for (auto i : f)
        if (i - 1 >= 0 && A[i-1])
            moves[i-1] = 1;
    
    for (int pos = 0; pos < N; pos++) {
        if (A[pos] == 0)
            continue;

        for (int i = f.size()-1; i >= 0; i--) {
            if (pos + f[i] < N && A[pos + f[i]]) {
                moves[pos + f[i]] = min(moves[pos]+1, moves[pos + f[i]]);
            }
        }
    }
    if (moves[N - 1] != oo) {
        return moves[N - 1];
    }
    return -1;
}