动态规划:)
用1-n n个数字做BST的节点,其总数,为:用1做根节点得到的BST总数,加上用2做根节点得到的BST总数,加上用3做根节点得到的BST总数......,以此类推,最后加上用n做根节点得到的BST总数。
用k做根节点得到的BST总数,就是根节点k左侧需要用1,2,3...,k-1这些节点组成一个BST,假设有l种方法;根节点k右侧需要用k+1, k+2,...n这些节点组成一个BST,假设有r种方法。用k做根节点得到的BST总数,就有l*r种方法。
问题变成了如何求1,2,3...,k-1这些节点组成一个BST的数目?这就是原问题,现在n换成了k - 1:)
如何求k+1, k+2,...n这些节点组成一个BST的数目?其实,这和用1,2,3,...n-k这些节点组成一个BST的数目是一样的,所以,这也是原问题,现在n换成了n-k:)
所以,我们可以递归的求解,在最底层,用0个数字或者1个数字组成BST的数目,为1:)
如果学习了我的《玩转算法面试课程》(https://coding.imooc.com/class/82.html),就会理解,这个过程显然有重叠子问题。首先可以将递归改成记忆化搜索,进而,可以改写成动态规划:)
参考代码(C++):
记忆化搜索:https://github.com/liuyubobobo/Play-Leetcode/blob/master/0096-Unique-Binary-Search-Trees/cpp-0096/main.cpp
动态规划:https://github.com/liuyubobobo/Play-Leetcode/blob/master/0096-Unique-Binary-Search-Trees/cpp-0096/main2.cpp
加油!:)