Unique Binary Search Trees

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?

Example:

Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

这题跟上一题类似，这两题是以前遗漏的题目，应该是那时候想不出来该怎么做。好久不做题了，现在重新看看，其实不难，一眼就看出来怎么做了，可能刷题还是可以提升自己的算法能力的吧。

这题比上提简单，思路还是不断的构造左右子树来确定某个值能构造的数量。核心思想是动态规划。

动态规划的关键在于推导，将前面的结果作缓存，后续的运算将会使用到缓存的结果。我们把dp的数组定义为N个节点可以产生的所有树的可能性。

我们可以梳理一下思路，假设有1个节点，那么左右节点分别是0，我们把0节点看做一个特殊的节点值，值为1，那么1个节点能组成的数的个数就是1*1为1。

假设有2个节点，那么左右节点可以有以下两种情况：

• 左0右1。 在这种情况下，可能产生的组合总数为1
• 左1右0。 在这种情况下，可能产生的组合总数为1

由此我们可以看出，当N=2的时候，可能产生的树的数量为2

假设有3个节点，那么左右节点可以有以下三种情况：

• 左0右2. 在这种情况下，可能产生的组合总数为1*2=2
• 左1右1. 在这种情况下，可能产生的组合总数为1*1=1
• 左2右0. 在这种情况下，可能产生的组合总数为2*1=2

由此当N=3的时候，可能产生的数的数量为5.

由此递推公式已经产生了。

下面贴一下我的实现，打败了100%的实现。

    int numTrees(int n) {
        if (n == 0) {
            return 0;
        }

        vector<int> dp(n + 1);
        dp[0] = 1;

        for (int dpi = 1; dpi <= n; dpi++) {
            int dpv = 0;
            for (int i = 1; i <= dpi; i++) {
                dpv += dp[i - 1] * dp[dpi - i];
            }
            dp[dpi] = dpv;
        }

        return dp[n];
    }