1. Идея

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

Например, для 4 разбиения такие:

• 4
• 3 + 1
• 2 + 2
• 2 + 1 + 1
• 1 + 1 + 1 + 1

Всего 5.

Это классическая задача на динамическое программирование, очень похожая на подсчёт числа способов набрать сумму, если можно использовать числа 1, 2, ..., n сколько угодно раз, а порядок использования не учитывается.

Будем хранить dp[s] — количество способов получить сумму s.

2. Наблюдения

Наблюдение 1

Если разрешить использовать только числа от 1 до x, то можно постепенно наращивать ответ.

Сначала учитываем только 1, потом 1 и 2, потом 1, 2, 3 и так далее.

Наблюдение 2

Когда мы добавляем очередное число x, для каждой суммы s >= x можно:

• не использовать x,
• или использовать его хотя бы один раз.

Если использовать x хотя бы один раз, то после выбора одного x остаётся добрать сумму s - x, и это можно сделать всеми способами, уже посчитанными в dp[s - x].

Поэтому переход такой:

dp[s] += dp[s - x]

Наблюдение 3

Очень важно, в каком порядке идти по циклам.

Если внешний цикл идёт по x от 1 до n, а внутренний — по s от x до n, то каждое разбиение будет посчитано ровно один раз, без учёта перестановок.

Именно поэтому разбиения 1 + 3 и 3 + 1 не считаются отдельно.

3. Алгоритм

1. Считываем n.
2. Создаём массив dp длины n + 1, заполненный нулями.
3. Полагаем dp[0] = 1.
   • Это означает, что сумму 0 можно получить ровно одним способом: ничего не взять.
4. Для каждого числа x от 1 до n:
   • для каждой суммы s от x до n:
     • прибавляем к dp[s] значение dp[s - x];
     • берём результат по модулю 1000000007.
5. Выводим dp[n].

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

Докажем, что после обработки всех чисел от 1 до x значение dp[s] равно числу разбиений суммы s на слагаемые, не превосходящие x.

База

До начала циклов:

• dp[0] = 1,
• dp[s] = 0 для s > 0.

Это верно: сумму 0 можно получить одним способом, а положительные суммы — никак, если ещё не разрешено использовать никакие числа.

Переход

Пусть уже после обработки чисел от 1 до x - 1 всё посчитано правильно.

Теперь добавляем число x.

Для каждой суммы s:

• старое значение dp[s] — это число разбиений s, где число x не используется;
• значение dp[s - x], которое прибавляется, соответствует разбиениям суммы s - x с числами до x, а если к каждому такому разбиению добавить одно слагаемое x, получится разбиение суммы s, где x используется хотя бы один раз.

Эти два множества разбиений не пересекаются и вместе дают все разбиения суммы s с числами до x.

Значит, после обновления:

• dp[s] становится числом всех разбиений s на слагаемые не больше x.

Почему порядок не учитывается

Поскольку мы добавляем числа в порядке возрастания: сначала 1, потом 2, потом 3 и так далее, — каждое разбиение строится в единственном виде: как набор слагаемых, отсортированных по неубыванию.

Поэтому перестановки одинаковых слагаемых не создают новых способов.

Следовательно, после завершения всех циклов dp[n] — это именно количество разбиений числа n на натуральные слагаемые без учёта порядка.

5. Сложность

Внешний цикл выполняется n раз.

Внутренний цикл для каждого x проходит по суммам от x до n, то есть суммарно это O(n^2) операций.

• Время: O(n^2)
• Память: O(n)

При n <= 5000 это укладывается в ограничения.

6. Код на C++17

#include <iostream>
#include <vector>

using namespace std;

int main() {
    const long long MOD = 1000000007LL;

    int n;
    cin >> n;

    vector<long long> dp(n + 1, 0);
    dp[0] = 1;

    for (int x = 1; x <= n; x++) {
        for (int s = x; s <= n; s++) {
            dp[s] += dp[s - x];
            if (dp[s] >= MOD) dp[s] -= MOD;
        }
    }

    cout << dp[n] << '\n';
    return 0;
}

7. Код на Python 3

MOD = 1000000007

n = int(input())

dp = [0] * (n + 1)
dp[0] = 1

for x in range(1, n + 1):
    for s in range(x, n + 1):
        dp[s] += dp[s - x]
        if dp[s] >= MOD:
            dp[s] -= MOD

print(dp[n])