Изменения

__TOC__

Пусть <tex>P(n, m, k)</tex> — количество разбиений числа <tex>n</tex> на <tex>m</tex> слагаемых, каждое из которых не превосходит <tex>k</tex>.

Имеет место следующее рекуррентное соотношение:

Начальные значения динамики <tex>d[n][m][k] = -1</tex>. Ответ на исходную задачу равен <tex>\sum\limits_{i=0}^nPartition(n, i, n)</tex>. Асимптотика <tex>O(n^{3})</tex>.

Обозначим <tex>P(n,k)</tex> — количество разбиений числа <tex>n</tex> на слагаемые, каждое из которых не превосходит <tex>k</tex>. Оно удовлетворяет следующей рекурентной формуле:<p>

<tex dpi="145">P(n,k) = \left \{ \begin{array}{ll} P(n,k - 1) + P(n - k, k), & k \leqslant n \\ P(n, n), & k > n \end{array} \right.</tex>

</p>

Рассмотрим самый быстрый алгоритм нахождения количества разбиений числа <tex>n</tex> на слагаемые, который работает за <tex> O(n \sqrt{n}) </tex>.

Так как мы рассматриваем лишь разбиения на различные слагаемые, то диаграммы таких разбиений состоят из нескольких трапеций, поставленных друг на друга. Обозначим число точек в верхней строке диаграммы через <tex>m</tex>, а число строк нижней трапеции через <tex>n</tex> (на рис. 1 слева изображена диаграмма, для которой <tex>m=2</tex>, <tex>n=3</tex>).

'''Преобразование 1.''' Предположим, что диаграмма содержит не менее двух трапеций, причем <tex>m \leqslant n</tex>. В этом случае отбросим первую строку из <tex>m</tex> точек, но удлиним последние <tex>m</tex> строк нижней трапеции на одну точку(рис. 1). После этого общее число точек не изменится, все строки окажутся различной длины, но четность числа строк изменится.