// брой partition-и на число n за O(n^2)

#include <iostream>
using namespace std;

const int M = 1000;

int memo[M][M];

// брой partition-и на n, най-малкото число, в които е >= i
int partitions(int i, int n)
{
	if (i > n) return 0;
	if (memo[i][n] != -1) return memo[i][n];
	return memo[i][n] = partitions(i + 1, n) + partitions(i, n - i);
}

int main()
{
	for (int i = 1; i < M; i++) for (int j = 0; j < M; j++) memo[i][j] = -1;
	for (int i = 1; i < M; i++) memo[i][i] = 1;

	cout << partitions(1, 10) << endl; // брой partition-и на 10

	return 0;
}