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