递归并非万能

递归的确简洁, 但性能很差, 因为它进行了大量重复的计算,
如果用递归运算做乘法, 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()