Comments 18
Насколько я понимаю, после каждой итерации нужно получать верёвки минимальной длинны, т.е. по сути мы создаем массив из длин веревок и соединяем первую и последнюю, вторую и предпоследнюю и тд, и так на каждой итерации.
Это очень сильно напоминает главу из книги Перельмана ("Занимательная арифметика" если не ошибаюсь) где учитель дал ученикам задачу сложить все числа от 1 до 100..
И одним из этих учеников был Гаусс, да? =)
Но почему в Вашем решении получится оптимальная стоимость всё-таки?
не знаю, интуиция)
а вот объясните мне, пожалуйста, откуда вот тут 39 взялось:
Сначала соединим 10 и 5, потом соединим 21 и 3, после чего соединим две полученные верёвки. Стоимость: 15+24+39=78.
мы же соединили
1) 10 + 5 = 15,
2) 21 + 3 = 24,
3) 24 + 15 = 39
Ответ: 39
Или я неправильно условие задачи понимаю?
Cracking the Coding Interview + LeetCode?
Интуитивно, на каждом шаге нужно соединять две самые короткие на данный момент верёвки.
Достаточно доказать, что можно первым шагом две минимальные веревки объединить. А дальше, после первого шага, задача сводится к той же самой.
Если представить дерево, как эти веревки сливаются, то там листья — это входные числа, а промежуточные вершины отвечают объединениям. Каждый лист посчитается в ответе ровно столько раз, какая у него глубина. Значит можно жадно минимальные веревки запихивать как можно глубже. Не факт, что это уже будет оптимальный ответ, ведь может самое дерево надо переформатировать, но то, что в оптимальном ответе первый шаг, это две минимальные веревки, уже доказано.
Из России как оплатить можно? Мир не принимает, платеж визой не проходит, якобы потому что банк отклоняет, но подозреваю, что из-за ограничений визы.
Оказывается, что из России никак, к сожалению. Я вот и сам этого не знал.
Интерактивный учебник для подготовки к алгоритмической секции собеседования