270. dp

#include <vector>
#include <iostream>

using namespace std;
typedef long long ll;


int main()
{
    int n;
    cin >> n;
    vector<vector<vector<int> > > dp(n+1,vector<vector<int> >(n+1, vector<int>(n+1)));
    for (int i(1); i < n+1; i++)
    {
        dp[i][1][i] = 1;
    }
    for (int i(2); i < n+1; i++)    //кол-во звезд
    {
        for (int k(2); k < n+1; k++)    // кол-во слоев
        {
            for (int j(k); j <= i; j++) //кол-во звезд на last уровне
            {
                if (i - j > 0)
                {
                    int u = i - j;
                    for (int m(1); m < j; m++)
                    {
                        dp[i][k][j] += dp[u][k - 1][m];
                    }
                }
            }
        }
    }
    int sum(0);
    for (int i(0); i < n + 1; i++)
    {
        for (int j(0); j < n + 1; j++)
        {
            sum += dp[n][i][j];
        }
    }
    cout << sum;
    return 0;
}