Разработать функцию, которая находит минимальный путь в треугольнике чисел (динамическое программирование).

Минимальный путь в треугольнике чисел

Функция minimum_total находит минимальный путь с вершины до основания треугольника, который представлен в виде списка списков, где каждый внутренний список содержит числа на соответствующем уровне треугольника.

def minimum_total(triangle):
    if not triangle:
        return 0
    # Копирование последнего ряда в виде начального состояния для динамического программирования
    min_path = triangle[-1]
    # Переход от предпоследнего ряда к вершине треугольника
    for i in range(len(triangle) - 2, -1, -1):
        for j in range(len(triangle[i])):
            # Обновляем текущий элемент, выбирая минимальный путь
            min_path[j] = triangle[i][j] + min(min_path[j], min_path[j + 1])
    # Возвращаем минимальный элемент, который теперь находится в вершине треугольника
    return min_path[0]

# Пример использования:
triangle = [
    [2],
    [3, 4],
    [6, 5, 7],
    [4, 1, 8, 3]
]
print("Минимальный путь: ", minimum_total(triangle))

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

Категория: Практические упражнения Python | Добавил: Admin (03.05.2024)
Просмотров: 18 | Рейтинг: 0.0/0
Всего комментариев: 0
Имя *:
Email *:
Код *: