递归的确简洁, 但性能很差, 因为它进行了大量重复的计算,
如果用递归运算做乘法,5!*4! = 5*4*3*2*1 * 4*3*2*1显然4!完全可以算一遍, 而递归结结实实的算了两遍
如果我们把每一步运算的结果都用字典存起来, 那就能减少大量的运算
分享一道题目:
给出1, 2, 3, 4, 5, ..., n 一共n个数, 求用它们能够构成多少种形状不同的二叉搜索树
二叉搜索树 "左节点的值大于右节点"
二叉搜索树
class Solution:
def __init__(self):
self.ubs_dic = {0: 0, 1: 1}
def numTrees(self, n):
# 要求n的就必须把前面所有的项都求出来
for k in range(n+1):
tmp = 0
for now_k in range(k):
pre_left = self.ubs_dic[now_k]
pre_right = self.ubs_dic[k-now_k-1]
if pre_left == 0:
pre_left = 1
if pre_right == 0:
pre_right = 1
tmp = tmp + (pre_left * pre_right)
self.ubs_dic[k] = tmp
return self.ubs_dic[n]
def main():
so = Solution()
result = so.numTrees(10)
print(result)
if __name__ == '__main__':
main()
