# A 17-Line 2-D Tabular DP Solution with Explanations

• ``````// DP[i,j] means all the possible sub trees contrstructed by nodes from i to j.
// DP[1,1], DP[2,2] ... are List<TreeNode> with a single node, and they
// are initiated at beginning.
// DP[i,0] and DP[i, i-1] are List<TreeNode> with a Null node
// which are prepared for connecting null left/right nodes
// Loop from left-up to right-bottom each line per loop cycle, until (1, n)
//    0  1  2  3  4  5  6  7 (n)
// 0 [ ][ ][ ][ ][ ][ ][ ][ ][ ]
// 1 [X][1][ ][ ][ ][ ][ ][ ][ ]
// 2 [X][X][2][ ][ ][ ][ ][ ][ ]
// 3 [X][ ][X][3][ ][ ][ ][ ][ ]
// 4 [X][ ][ ][X][4][ ][ ][ ][ ]
// 5 [X][ ][ ][ ][X][5][ ][ ][ ]
// 6 [X][ ][ ][ ][ ][X][6][ ][ ]
// 7 [X][ ][ ][ ][ ][ ][X][7][ ]
//(n)[X][ ][ ][ ][ ][ ][ ][X][n]
//n+1[X][ ][ ][ ][ ][ ][ ][ ][X]

public IList<TreeNode> GenerateTrees(int n) {
List<TreeNode>[,] DP = new List<TreeNode>[n + 2, n + 1];
for (int i = 1; i <= n + 1; i++)
for(int j = 0; j <= n; j++){
DP[i, j] = new List<TreeNode>();
if(i == j) DP[i, j].Add(new TreeNode(i));
else if (j == 0 || j == i - 1) DP[i, j].Add(null);
}
for (int cycle = n - 1; cycle >= 1; cycle--)
for (int i = 1, j = n - cycle + 1; i <= cycle; i++, j++)
for (int k = i; k <= j; k++)
foreach (var leftNode in DP[i, k - 1])
foreach (var rightNode in DP[k + 1, j]){