# My iterative DP solution (C++)

• ``````class Solution {
public:

vector<TreeNode *> generateTrees(int n) {
if( n < 1 ) return vector< TreeNode *>(1);
vector<TreeNode*> rootMem[ 100 ][ 100 ];// rootMem[ i ][ j ] stores the tree from j with length i
for( int j = 0; j <= n + 1; j++ )           //Init. It should be noted that j = 0 and j = n + 1 must be inited
{
TreeNode * tmp = new TreeNode( j );
rootMem[ 1 ][ j ].push_back( tmp );
tmp = NULL;
rootMem[ 0 ][ j ].push_back( tmp );
}
for( int i = 2; i <= n; i++ )//Length from 2 to n
{
for( int j = 1; j <= n - i + 1; j++ )// the smallest cannot exceed n - i + 1. n - i + 1  + i  -1 = n
{
for( int k = 0; k < i; k++ )
{
for( int left = 0; left < rootMem[ k ][ j ].size(); left++ )
{
for( int right = 0; right < rootMem[ i - k - 1 ][ j + k + 1].size(); right++ )
{
TreeNode * tmp = new TreeNode( k + j );
tmp->left  = rootMem[ k ][ j ][ left ];
tmp->right = rootMem[ i - k - 1 ][ j + k + 1][ right ];
rootMem[ i ][ j ].push_back( tmp );
}
}
}
}
}
return rootMem[ n ][ 1 ];

}
};``````