Разработать функцию, которая находит минимальный путь в треугольнике чисел (динамическое программирование).
Минимальный путь в треугольнике чиселФункция
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))
Эта функция использует метод динамического программирования для упрощения задачи, начиная с нижнего уровня треугольника и поднимаясь к вершине, обновляя значения на основе минимальных путей снизу вверх. | |
|
| |
| Просмотров: 195 | |
| Всего комментариев: 0 | |