请稍等 ...
×

采纳答案成功!

向帮助你的同学说点啥吧!感谢那些助人为乐的人

正在回答

插入代码

1回答

liuyubobobo 2018-09-10 15:28:26

动态规划:)


用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 


加油!:)


0 回复 有任何疑惑可以回复我~
问题已解决,确定采纳
还有疑问,暂不采纳
意见反馈 帮助中心 APP下载
官方微信