Задачка для скучающих: Оригинал https://www.codewars.com/kata/pyramid-slide-down Есть генератор пирамид из чисел, пример: .....3 ...7 4

Question

Задачка для скучающих: Оригинал https://www.codewars.com/kata/pyramid-slide-down Есть генератор пирамид из чисел, пример: .....3 ...7 4

..2 4 6
.8 5 9 3
Нужно найти путь от верха к основанию (или наоборот), переходя только к соседним числам от предыдущего, чтобы сумма чисел была самой большой. Автор рекомендует не использовать брутфорс, т.к. пирамиды могут быть слишком большими.
Какие мысли по алгоритму ?

#backend #programming #python #russian

0

06.07.2018

4 ответов

41 просмотр

Tigran Saluev

Очевидное DP

0

06.07.2018

Tigran Saluev

Идём снизу вверх, для каждого числа вычисляем самый дорогой путь от него вниз. Алгоритм за О(количество чисел в пирамиде) и памятью О(высота пирамиды) (при грамотной организации).

0

06.07.2018

Tishka17

Идем снизу вверх. Для нижнего ряда ничего не делаем. Для второго снизу для каждого элемента: запоминаем с какой стороны ниже число больше и полученную сумму. Для третьего снизу аналогично: где снизу сумма больше и новую сумму. В итоге доходим до верха и там уже имеем сумму и первое направление

0

06.07.2018

Aragaer · Accepted Answer

Aragaer

я бы шел снизу вверх - для каждой под-пирамиды Н-ного уровня находил бы наиболее крутую этого уровня (но продолжал держать список всех)

0

06.07.2018

170 похожих чатов

Задачка для скучающих: Оригинал https://www.codewars.com/kata/pyramid-slide-down Есть генератор пирамид из чисел, пример: .....3 ...7 4

4 ответов

Похожие вопросы