Задача 752. 2-3 Дерево
Задача из раздела комбинаторика, но на мой взгляд - это в чистом виде динамическое программирование. Давайте разбираться: Давайте посмотрим на последний ряд дерева. Понятно, что все листья разбиваются на группы по 2 или 3. Научимся считать количество разбиений методом динамического программирования. База динамики: 2, 3 и 4 элемента разбиваются единственным способом. Шаг динамики, если все ответы до i элементов посчитаны: какой могла быть последняя группа? Всё те же 2 или 3 элемента, то есть ответ для задачи размера i складывается из ответов для подзадач размера i - 2 и i - 3...
4 года назад
Разбор задачи "Сумма степеней двойки". Тема: динамическое программирование
Ещё одна интересная задача. Поначалу она может показаться чисто математической, но суть решения кроется совсем не в этом :) Собственно, задание: Любое натуральное число можно представить в виде суммы натуральных слагаемых, каждое из которых является степенью числа 2. Суммы, различающиеся лишь порядком слагаемых, считаются одинаковыми. Например, для числа 7 таких представлений 6 (4+2+1, 4+1+1+1, 2+2+2+1, 2+2+1+1+1, 2+1+1+1+1+1, 1+1+1+1+1+1+1). Требуется написать программу, которая найдет количество способов такого представления заданного числа N...