1
class Solution:
2
    def uniquePaths(self, m: int, n: int) -> int:
3
        # 初始化一个 m 行 n 列的二维数组用于备忘录
4
        self.memo = [[0] * n for _ in range(m)]
5
        return self.dp(m - 1, n - 1)
6

7
    def dp(self, x, y):
8
        # 起点只有一种走法
9
        if x == 0 and y == 0:
10
            return 1
11
        # 越界情况直接返回 0
12
        if x < 0 or y < 0:
13
            return 0
14
        # 如果备忘录中已有结果，直接返回
15
        if self.memo[x][y] > 0:
16
            return self.memo[x][y]
17
        # 状态转移：从上方或左方走到当前位置
18
        self.memo[x][y] = self.dp(x - 1, y) + self.dp(x, y - 1)
19
        return self.memo[x][y]

1
class Solution:
2
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
3
        m, n = len(obstacleGrid), len(obstacleGrid[0])
4
        # 备忘录初始化为 0
5
        self.memo = [[0] * n for _ in range(m)]
6
        return self.dp(m - 1, n - 1, obstacleGrid)
7

8
    def dp(self, x, y, obstacleGrid):
9
        # 遇到障碍物，无法通行
10
        if obstacleGrid[x][y] == 1:
11
            return 0
12
        # 起点，如果没有障碍，则返回 1
13
        if x == 0 and y == 0:
14
            return 1
15
        # 越界处理
16
        if x < 0 or y < 0:
17
            return 0
18
        # 如果该点已有计算结果，直接返回
19
        if self.memo[x][y] > 0:
20
            return self.memo[x][y]
21
        # 状态转移
22
        self.memo[x][y] = self.dp(x - 1, y, obstacleGrid) + self.dp(x, y - 1, obstacleGrid)
23
        return self.memo[x][y]

1
class Solution:
2
    def integerBreak(self, n: int) -> int:
3
        # 初始化备忘录
4
        self.memo = [-1] * (n + 1)
5
        return self.dp(n)
6

7
    def dp(self, n):
8
        # 递归出口：n=0 时无法继续拆分，返回 0
9
        if n == 0:
10
            return 0
11
        if n == 1:
12
            return 1
13
        # 已计算过的直接返回
14
        if self.memo[n] > 0:
15
            return self.memo[n]
16
        res = float('-inf')
17
        # 尝试每一种拆分 i + (n - i)，选择最大乘积
18
        for i in range(1, n):
19
            # 两种情况：继续拆分(n-i) or 不拆(n-i)
20
            res = max(res, i * max(self.dp(n - i), n - i))
21
        self.memo[n] = res
22
        return res

1
class Solution:
2
    def numTrees(self, n: int) -> int:
3
        # 初始化一个二维备忘录 memo[l][r]
4
        self.memo = [[0] * (n + 1) for _ in range(n + 1)]
5
        return self.dp(1, n)
6

7
    def dp(self, l, r):
8
        # 空区间或单节点都只有一种 BST 结构
9
        if l >= r:
10
            return 1
11
        # 已有结果，直接返回
12
        if self.memo[l][r] != 0:
13
            return self.memo[l][r]
14

15
        res = 0
16
        # 枚举所有可能的根节点 i
17
        for i in range(l, r + 1):
18
            # 左子树为 [l, i-1]，右子树为 [i+1, r]
19
            left = self.dp(l, i - 1)
20
            right = self.dp(i + 1, r)
21
            # 左右子树组合数相乘
22
            res += left * right
23
        self.memo[l][r] = res
24
        return res