Short Problem Definition:
Count the minimum number of jumps required for a frog to get to the other side of a river.
Link
Complexity:
expected worst-case time complexity is O(N\*log(N))
expected worst-case space complexity is O(N)
Execution:
This problem can be solved by in a Dynamic Programming way. You need to know the optimal count of jumps that can reach a given leaf. You get those by either reaching the leaf from the first shore or by reaching it from another leaf.
The N*log(N) time complexity is given by the fact, that there are approximately log(N) Fibonacci numbers up to N and you visit each position once.
As for the sequence hack: there are 26 Fibonacci numbers smaller than 100k, so I just preallocate an array of this size.
Solution:
def get_fib_seq_up_to_n(N):
# there are 26 numbers smaller than 100k
fib = [0] * (27)
fib[1] = 1
for i in xrange(2, 27):
fib[i] = fib[i - 1] + fib[i - 2]
if fib[i] > N:
return fib[2:i]
else:
last_valid = i
def solution(A):
# you can always step on the other shore, this simplifies the algorithm
A.append(1)
fib_set = get_fib_seq_up_to_n(len(A))
# this array will hold the optimal jump count that reaches this index
reachable = [-1] * (len(A))
# get the leafs that can be reached from the starting shore
for jump in fib_set:
if A[jump-1] == 1:
reachable[jump-1] = 1
# iterate all the positions until you reach the other shore
for idx in xrange(len(A)):
# ignore non-leafs and already found paths
if A[idx] == 0 or reachable[idx] > 0:
continue
# get the optimal jump count to reach this leaf
min_idx = -1
min_value = 100000
for jump in fib_set:
previous_idx = idx - jump
if previous_idx < 0:
break
if reachable[previous_idx] > 0 and min_value > reachable[previous_idx]:
min_value = reachable[previous_idx]
min_idx = previous_idx
if min_idx != -1:
reachable[idx] = min_value +1
return reachable[len(A)-1]