刷算法-- leetcode 96. 不同的二叉搜索树

思路

1. 观察树的组成，可以发现n=3时的二叉搜索树可以由，头节点分别为1、2、3时的所有结果组成！
2. 定义dp[i]为由i个节点组成的二叉搜索树的个数。
3. 确定递推公式，dp[i] = 由1为头节点组成的二叉搜索树个数+由2为头组成的个数+…+由i为头节点组成的个数。
   所以，进一步分析：
   1. 由1为头节点组成的二叉搜索树个数=左子树个数为0时搜索树个数*右子树节点数为2时的搜索树个数.
   2. 由2为头节点时组成的搜索树个数=左子树包含1个节点是的搜索树个数*右子树节点数为2时的搜索树个数
      节点数量为2时的搜索树个数=dp[2]
      节点数量为1时的搜索树个数=dp[1]
4. 所以，dp[3] = dp[0]*dp[2] + dp[1]*dp[1] + dp[2]*dp[0];
5. 可以看出上述公式是一种交错的关系。使用双重循环去递推。