Изменения

__TOC__

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

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

Количество всех разбиений числа равно <tex>\sum\limits_{i=0}^nP(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 \{

Количество всех разбиений числа <tex>n</tex> равно <tex>P(n,n)</tex>. Асимптотика <tex>O(n^{2})</tex>.

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