10
правок
Изменения
Нет описания правки
разбиения, которые не содержат в качестве старшего слагаемого <tex>k</tex>. Таких разбиений <tex>P(n, m, k - 1)</tex>. Во второй — все разбиения со старшим слагаемым <tex>k</tex>. Их столько же, сколько разбиений числа <tex>n - k</tex> на <tex>m - 1</tex> слагаемое, каждое из которых не больше <tex>k</tex>, то есть <tex>P(n - k, m - 1, k)</tex>.
Количество всех разбиений числа равно <tex>\sum\limits_{i=0}^nP(n, i, n)</tex>. Реализация данного алгоритма методом [[Динамическое программирование|динамического программирования ]] с мемоизацией будет иметь асимптотику <tex>O(n^{3})</tex>.
== Алгоритм за O(N<sup>2</sup>) ==
