Даю 20баллов!!! Только на C++!!!!!

Количество разбиений на слагаемые

Дано натуральное число N. Найдите количество его разбиений на натуральные слагаемые. Два разбиения, отличающиеся только порядком слагаемых, будем считать за одно.


Например, для N=5 существует 7 различных разбиений:


5=5

5=4+1

5=3+2

5=3+1+1

5=2+2+1

5=2+1+1+1

5=1+1+1+1+1

Входные данные


Задано единственное число N≤30.


Выходные данные


Выведите количество различных разбиений на слагаемые.


Примеры

Ввод 5

Вывод 7

В помощь видео!!!!
youtube
/watch?v=MrdTbJ5zKsQ

Это задача на количество разбиений числа (partition function), где порядок слагаемых не важен.

Идея решения

Нужно найти, сколькими способами можно представить число N как сумму натуральных чисел, не различая перестановки.

Это классическая задача динамического программирования.

Обозначим:

• dp[i] — количество разбиений числа i.

Но удобнее строить ответ иначе:
мы будем последовательно добавлять слагаемые от 1 до N.

Переход

Изначально:

• dp[0] = 1 (есть один способ ничего не выбрать)

Далее для каждого числа i от 1 до N:

• обновляем dp так, чтобы учитывать использование числа i как слагаемого

Формула:

dp[j] += dp[j - i]

где j идёт от i до N.

Такой порядок гарантирует, что разбиения не будут считаться в разных перестановках.

Почему это работает

Мы как бы говорим:

• сначала используем 1

• потом 2

• потом 3
  и т.д.

Таким образом мы строим разбиения в неубывающем порядке, избегая повторов.

C++ решение

C++
#include 
using namespace std;

int main() {
    int N;
    cin >> N;

    long long dp[31] = {0};
    dp[0] = 1;

    for (int i = 1; i <= N; i++) {
        for (int j = i; j <= N; j++) {
            dp[j] += dp[j - i];
        }
    }

    cout << dp[N];
    return 0;
}

Сложность

• Время: O(N²)

• Память: O(N)

Для N ≤ 30 работает мгновенно.