7.4 — Пример 2. Голодный кролик

Представь кролика в начале числовой линии (в точке 0).

В некоторых точках лежат морковки разного размера.
В точке x находится нора.
Кролик может прыгать только на 1, 2 или 3 клетки вперёд.

Задача: кролик хочет добраться до норы и съесть как можно больше морковки.

Кролик, морковки и нора на числовой прямой

Идея решения

Как кролик может попасть в клетку y?

из y-1,
из y-2,
или из y-3.

Если мы уже знаем, сколько морковок можно собрать в этих точках, то для y остаётся только выбрать лучший из трёх вариантов и прибавить морковку в клетке y.

def hangry_bunny(line, x):
    # line[i] — количество морковок в точке i
    carrots = [0] * (x + 1)
    carrots[0] = line[0]  # старт

    for i in range(1, x + 1):
        # смотрим, из каких 3 предыдущих точек кролик мог прийти
        for j in range(max(0, i - 3), i):
            carrots[i] = max(carrots[i], carrots[j] + line[i])

    return carrots[x]

# Пример
line = [0, 5, 1, 2, 10, 2, 4]  # морковки в точках
x = 6  # нора в точке 6
print(hangry_bunny(line, x))  #21

Сложность алгоритма: O(n).

Для каждой клетки мы смотрим не более трёх предыдущих.

А теперь представь, что мы бы делали полный перебор — вариантов прыжков оказалось бы очень много, и программа считала бы целую вечность. А так — динамика спасает!

Голодный кролик с маршрутом

def hangry_bunny_with_path(line, x):
    # line[i] — морковки в точке i
    carrots = [0] * (x + 1)     # максимум морковок в каждой точке
    path = [-1] * (x + 1)       # откуда пришёл кролик

    carrots[0] = line[0]  # старт с первой клетки

    for i in range(1, x + 1):
        for j in range(max(0, i - 3), i):
            # если из j выгоднее прыгнуть, обновляем
            if carrots[j] + line[i] > carrots[i]:
                carrots[i] = carrots[j] + line[i]
                path[i] = j  # запоминаем, откуда пришёл

    # восстановим маршрут
    route = []
    current = x
    while current != -1:
        route.append(current)
        current = path[current]

    route.reverse()  # маршрут от старта до финиша
    return carrots[x], route

# Пример
line = [0, 5, 1, 2, 10, 2, 4]  # морковки в точках
x = 6  # нора в точке 6

max_carrots, route = hangry_bunny_with_path(line, x)
print("Максимум морковок:", max_carrots)
print("Маршрут кролика:", route)

Таким образом мы сделали алгоритм нагляднее: теперь видно и результат, и сам путь.

Пример 2. Голодный кролик

Материал урока

Идея решения

Голодный кролик с маршрутом