Consider keys $[ 1 \ldots n]$. We want to calculate probability that BST tree has height = $h$. (We assume that distribution is uniform over all $C_{n}$ trees, where $C_n$ - n-th Catalan number).
First of all of course we can calculate it via $dp[i][j]$ - number of tree with height $i$ and $j$ vertices, then we divide $dp[h][n]$ by $C_n$ and obtain the result, but it's hard to do using C++ (because $C_{40}$ is very huge and calculation will be incorrect).
Of course we can consider $dp[i][j]$ - is probability that tree has depth $i$ and contains $j$ vertices, but then dynamic step is slightly incorrect ($dp[i][j] = dp[i - k][h - 1] * dp[k][h - 1]$, but it also fail initial values of $dp[i][j]$).
Maybe I should reconsider my dp? Any ideas?