题解 | 二叉树

import sys
from typing import List
from functools import lru_cache
import bisect
n, m = map(int, input().split())

mod = 1000000007
class Solution:
    def computeWays(self, n: int, m: int) -> int:
        @lru_cache(None)    
        def dfs(n, m):
            if n == 0:
                return 1
            if m == 0:
                return 0
            ans = 0
            for k in range(n):
                ans = (ans + (dfs(n - k - 1, m - 1) * dfs(k, m - 1)) % mod) % mod
            return ans % mod
        return dfs(n, m)


# 测试用例：
solution = Solution()
print(solution.computeWays(n, m))