Answer the question
In order to leave comments, you need to log in
How to solve the grasshopper problem correctly using dynamic programming?
Hello! Wrote code to solve the following problem:
Grasshopper
Grasshopper jumps over flowers located on a straight line. Each flower contains pollen. At the beginning of the path, the grasshopper is on the ground.
Grasshopper can
def minimum(F: list):
pollen_array = []
if len(F) < 3:
pollen_array.append(0)
return F[1], pollen_array
elif len(F) == 3:
pollen_array.append(F.index(min(F[1], F[2])) - 1)
return min(F[1], F[2]), pollen_array
else:
pollen = 0
i = 0
while i < len(F) - 1:
if i < len(F) - 2:
pollen += min(F[i + 1], F[i + 2])
i = F.index((min(F[i + 1], F[i + 2])), i + 1) if F[i + 1] != F[i+2] else i + 2
pollen_array.append(i - 1)
elif i == len(F) - 2:
pollen += F[i + 1]
pollen_array.append(i)
break
return pollen, pollen_array
n = int(input())
F = list(map(int, input().split()))
F.insert(0, 0)
a, b = minimum(F)
print(a)
print(*b)
Answer the question
In order to leave comments, you need to log in
Didn't find what you were looking for?
Ask your questionAsk a Question
731 491 924 answers to any question