递归并非万能

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()