G
G
GeloBer2021-05-09 21:12:12
Python
GeloBer, 2021-05-09 21:12:12

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

  • jump to the next flower
  • jump over one flower

How can a grasshopper get from the ground to the last flower with less pollen.

Input data format
Two lines. In the first one - the number of flowers, N. In the second array of length N - the amount of pollen (from 1 to 100) on each flower.

Output data format
Two lines. In the first, the minimum amount of pollen that a grasshopper will get dirty with. In the second - the path of the grasshopper. The path represents the numbers of flowers that the grasshopper will visit. Flower numbering from scratch.

Examples
Input
3
1 3 1
Output
2
0 2

Input
4
2 1 5 1
Output
2
1 3

The problem with my code is that it fails some tests that are hidden from me. I checked the code on the notebook manually, everything seems to be working. Please explain what is the problem. Thanks in advance!
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

1 answer(s)
W
Wataru, 2021-05-09
@GeloBer

You understood that this is dynamic programming. Describe what kind of DP function you have, give the recalculation formula, base and where is the answer.

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question