Как правильно решить задачу про кузнечика путём динамического программирования?

Question

[GeloBer]

Всем привет! Написал код для решения следующей задачи:

Кузнечик
Кузнечик прыгает по цветам, расположенным на прямой. На каждом цветке находится пыльца. В начале пути кузнечик находится на земле.

Кузнечик может

• прыгнуть на следующий цветок
  
• перепрыгнуть один цветок
  

Как кузнечику добраться от земли до последнего цветка, запачкавшись меньшим количеством цветочной пыльцы.

Формат входных данных
Две строки. В первой - количество цветков, N. Во второй массив длины N - количество пыльцы (от 1 до 100) на каждом цветке.

Формат выходных данных
Две строки. В первой - минимальное количество пыльцы, которой запачкается кузнечик. Во второй - путь кузнечика. Путь представляет из себя номера цветков, которые посетит кузнечик. Нумерация цветков с нуля.

Примеры
Ввод
3
1 3 1
Вывод
2
0 2

Ввод
4
2 1 5 1
Вывод
2
1 3

Проблема моего кода в том, что он не проходит некоторые тесты, которые от меня скрыты. Проверял код на тетради в ручную, вроде бы всё работает. Прошу объяснить в чём проблема. Заранее спасибо!

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 1

[Wataru]

Вы поняли, что это динамическое программирование. Опишите, что у вас за функция ДП, дайте формулу пересчета, базу и где ответ.

Comments

[GeloBer]

F – это массив со значениями пыльцы; n – условно количество цветков(хотя я его вставил, чтобы тестирующая программа не ругалась); pollen – общее количество пыльцы, которое соберёт кузнечик и наконец, pollen_array – путь, по которому пройдёт кузнечик

[Wataru]

GeloBer, Вы знаете, как работает динамическое программирование? Без этого понимания вы задачу никогда не решите.

Минутка теории. При составлении решения через ДП надо определить 3 вещи:

1) Функция ДП. Назовем ее DP(). Эта функция дает ответ на какую-то задачу, заданную какими-то параметрами. Ее надо описать словами.
Потом мы сводим эту задачу к подзадачам, которое есть та же самая задача, но с другими параметрами. Это и будет рекуррентное соотношение.
Подсказка - в этой задаче параметр будет один - номер цветка/количество цветков от начала.

2) База. Для каких-то параметров надо задать значение функции DP(). Подсказка - тут надо задать DP(0).

3) Ответ. Наша функция может иметь больше параметров, чем есть в изначальной задаче. Поэтому надо указать, какие параметры DP дают ответ. В вашем случае ответом будет DP(n).

Опишите эти элементы и мы с вами сможем понять, почему ваш код делает что-то другое.

[GeloBer]

Wataru, функция, которую я написал, ищет наименьшее количество пыльцы. Я написал, что изначально значение пыльцы равно нулю, так как кузнечик стоит на земле. Затем описал два крайних случая, когда цветков два, либо один. Для общего случая также написал условие того, что если количество пыльцы на i+1 и i+2 цветках одинаково, то кузнечик прыгает на дальний. Ответ будет состоять, как я уже сказал, из общего количества пыльцы, в котором замарался кузнечик и его пути

[Wataru]

функция, которую я написал, ищет наименьшее количество пыльцы.

Вы же сами сказали, что она не работает на каких-то тестах. Значит она не ищет наименьшее количество пыльцы, а только пытается это сделать. У вас нет в коде какой-то простой ошибки, типа +1 где-то забыли. Его весь надо переписать с нуля.

Все, что вы говорите дальше - это не ДП. Это какой-то карго-культ. Вы, наверно, видели кучу программ реализующих ДП и как-то по подобию пытаетесь сделать. Но без понимания.

Еще раз, я призываю вас формализовать решение. Без этого вы не поймете решение задачи.

Перечитайте мой предыдущий комментарий. Что у вас функция DP(i) должна означать, если i - номер цветка, а в задаче вам надо минимизировать общее количество пыльцы полученной кузнечиком?

[GeloBer]

Wataru, спасибо за советы. Переписал код и задача решена. Хочется получить Ваш комментарий по поводу кода.

def minimum_pollen(f: list, n):
    c = [0] * len(f)
    c[0], c[1] = f[0], f[1]
    way = [[0]] * len(f)
    way[0], way[1] = [0], [1]
    for i in range(2, len(f)):
        c[i] = min(c[i - 1], c[i - 2]) + f[i]
        way[i] = way[c.index((min(c[i - 1], c[i - 2])), i - 2)] + [i]
    return c[n - 1], way[n - 1]


n = int(input())
f = list(map(int, input().split()))
tmp1, tmp2 = minimum_pollen(f, n)
print(tmp1)
print(*tmp2)

[Wataru]

GeloBer, работает в n раз медленнее, чем должно.

Во-первых, конструкция c.index путает. Код будет и короче и понятнее, если сделать тупо if else вместо min. В одной ветке берем i-1, в другой - i-2.

Во-вторых, вместо хранения списка посещенных цветков, вам надо для каждого цветка запомнить, какой из двух предыдущих дал минимум. И потом в цикле с последнего цветка надо пропрыгать по этим указателям, чтобы получить путь.

Поскольку вы на каждой итерации по i создаете список - ваше текущее решение работает за квадрат.

Восстановление ответа в конце, как я сказал, будет в итоге работать за линию.