打卡题目：leetcode第96题，二叉树的最大深度
    相似题目：95、98
    image.png

    【思路】
    对于n个节点的树，除了根节点外，节点在左子树和右子树的数目分布可能是左0右n-1，左1右n-1，…，左n-2右1，左n-1右0。
    用公式表示：dp[n]=dp[0]dp[n-1]+dp[1]dp[n-2]+…+dp[n-2]dp[1]+dp[n-1]dp[0]

    【代码】

    1. class Solution:
    2.     def numTrees(self, n: int) -> int:
    3.         if n < 2:
    4.             return n
    6.         dp = [0] * (n + 1)
    7.         dp[0], dp[1] = 1, 1
    8.         # dp[i] = dp[0] * dp[i - 1] + dp[1] * dp[i - 2] + ... + dp[i - 1] * dp[0]
    9.         for i in range(2, n + 1):
    10.             for j in range(i):
    11.                 dp[i] += dp[j] * dp[i - j - 1]
    12.         return dp[-1]