我正在处理下面提供的 Codility 问题，
斐波那契数列使用以下递归公式定义：
F(0) = 0
F(1) = 1
F(M) = F(M - 1) + F(M - 2) if M >= 2
一只小青蛙想要到河的对岸。青蛙最初位于河的一侧（位置-1）并想要到达另一侧（位置N）。青蛙可以跳过任意距离 F(K)，其中 F(K) 是第 K 个斐波那契数。幸运的是，河上有很多树叶，青蛙可以在树叶之间跳跃，但只能在位置N的河岸方向跳跃。
河上的树叶用由 N 个整数组成的数组 A 表示。数组 A 的连续元素代表河牌圈上从 0 到 N − 1 的连续位置。数组 A 仅包含 0 和/或 1：
0代表没有叶子的位置； 1表示包含叶子的位置。 目标是计算青蛙可以到达河对岸（从位置 -1 到位置 N）的最少跳跃次数。青蛙可以在位置 -1 和 N（河岸）以及每个包含叶子的位置之间跳跃。
例如，考虑数组 A：
A[0] = 0
A[1] = 0
A[2] = 0
A[3] = 1
A[4] = 1
A[5] = 0
A[6] = 1
A[7] = 0
A[8] = 0
A[9] = 0
A[10] = 0
青蛙可以进行三次长度为 F(5) = 5、F(3) = 2 和 F(5) = 5 的跳跃。
写一个函数：
class Solution { public int solution(int[] A); }
给定一个由 N 个整数组成的数组 A，返回青蛙可以到达河对岸的最小跳跃次数。如果青蛙无法到达河的另一边，该函数应返回 -1。
例如，给定：
A[0] = 0
A[1] = 0
A[2] = 0
A[3] = 1
A[4] = 1
A[5] = 0
A[6] = 1
A[7] = 0
A[8] = 0
A[9] = 0
A[10] = 0
该函数应返回 3，如上所述。
假使，假设：
N 是范围内的整数[0..100,000];
数组 A 的每个元素都是一个整数，可以具有以下值之一：0、1。
复杂：
预期最坏情况时间复杂度为O(N*log(N));
预期最坏情况的空间复杂度是O(N)（不计算输入参数所需的存储空间）。
我写了以下解决方案，
class Solution {
private class Jump {
int position;
int number;
public int getPosition() {
return position;
}
public int getNumber() {
return number;
}
public Jump(int pos, int number) {
this.position = pos;
this.number = number;
}
}
public int solution(int[] A) {
int N = A.length;
List<Integer> fibs = getFibonacciNumbers(N + 1);
Stack<Jump> jumps = new Stack<>();
jumps.push(new Jump(-1, 0));
boolean[] visited = new boolean[N];
while (!jumps.isEmpty()) {
Jump jump = jumps.pop();
int position = jump.getPosition();
int number = jump.getNumber();
for (int fib : fibs) {
if (position + fib > N) {
break;
} else if (position + fib == N) {
return number + 1;
} else if (!visited[position + fib] && A[position + fib] == 1) {
visited[position + fib] = true;
jumps.add(new Jump(position + fib, number + 1));
}
}
}
return -1;
}
private List<Integer> getFibonacciNumbers(int N) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < 2; i++) {
list.add(i);
}
int i = 2;
while (list.get(list.size() - 1) <= N) {
list.add(i, (list.get(i - 1) + list.get(i - 2)));
i++;
}
for (i = 0; i < 2; i++) {
list.remove(i);
}
return list;
}
public static void main(String[] args) {
int[] A = new int[11];
A[0] = 0;
A[1] = 0;
A[2] = 0;
A[3] = 1;
A[4] = 1;
A[5] = 0;
A[6] = 1;
A[7] = 0;
A[8] = 0;
A[9] = 0;
A[10] = 0;
System.out.println(solution(A));
}
}
然而，虽然正确性看起来不错，但性能还不够高。代码中是否存在错误以及如何提高性能？
通过简单的 BFS 获得 100% 的结果：
public class Jump {
int pos;
int move;
public Jump(int pos, int move) {
this.pos = pos;
this.move = move;
}
}
public int solution(int[] A) {
int n = A.length;
List < Integer > fibs = fibArray(n + 1);
Queue < Jump > positions = new LinkedList < Jump > ();
boolean[] visited = new boolean[n + 1];
if (A.length <= 2)
return 1;
for (int i = 0; i < fibs.size(); i++) {
int initPos = fibs.get(i) - 1;
if (A[initPos] == 0)
continue;
positions.add(new Jump(initPos, 1));
visited[initPos] = true;
}
while (!positions.isEmpty()) {
Jump jump = positions.remove();
for (int j = fibs.size() - 1; j >= 0; j--) {
int nextPos = jump.pos + fibs.get(j);
if (nextPos == n)
return jump.move + 1;
else if (nextPos < n && A[nextPos] == 1 && !visited[nextPos]) {
positions.add(new Jump(nextPos, jump.move + 1));
visited[nextPos] = true;
}
}
}
return -1;
}
private List < Integer > fibArray(int n) {
List < Integer > fibs = new ArrayList < > ();
fibs.add(1);
fibs.add(2);
while (fibs.get(fibs.size() - 1) + fibs.get(fibs.size() - 2) <= n) {
fibs.add(fibs.get(fibs.size() - 1) + fibs.get(fibs.size() - 2));
}
return fibs;
}