**描述**：给定一个整数 $n$。

**要求**：请生成返回以 $1$ 到 $n$ 为节点构成的「二叉搜索树」，可以按任意顺序返回答案。

**说明**：

- $1 \le n \le 8$。

**示例**：

- 示例 1：

输入：n = 3

输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

- 示例 2：

输入：n = 1

输出：[[1]]

如果根节点为 $i$，则左子树的节点为 $(1, 2, ..., i - 1)$，右子树的节点为 $(i + 1, i + 2, ..., n)$。可以递归的构建二叉树。

定义递归函数 `generateTrees(start, end)`，表示生成 $[left, ..., right]$ 构成的所有可能的二叉搜索树。

- 如果 $start > end$，返回 `[None]`。

- 遍历 $[left, ..., right]$ 的每一个节点 $i$，将其作为根节点。

- **时间复杂度**：$O(C_n)$，其中 $C_n$ 是第 $n$ 个卡特兰数。

- **空间复杂度**：$O(C_n)$，其中 $C_n$ 是第 $n$ 个卡特兰数。

**描述**：给定一个整数 $numRows$。

**要求**：生成前 $numRows$ 行的杨辉三角。

- 示例 2：

输入: numRows = 1

输出: [[1]]

定义状态 $dp[i][j]$ 为：杨辉三角第 $i$ 行、第 $j$ 列位置上的值。

根据观察，很容易得出状态转移方程为：$dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]$，此时 $i > 0$，$j > 0$。

- 每一行第一列都为 $1$，即 $dp[i][0] = 1$。

- 每一行最后一列都为 $1$，即 $dp[i][i] = 1$。

因为 $dp[i][j]$ 仅依赖于上一行（第 $i - 1$ 行）的 $dp[i - 1][j - 1]$ 和 $dp[i - 1][j]$，所以我们没必要保存所有阶段的状态，只需要保存上一阶段的所有状态和当前阶段的所有状态就可以了，这样使用两个一维数组分别保存相邻两个阶段的所有状态就可以实现了。

定义 $dp[j]$ 为杨辉三角第 $i$ 行第 $j$ 列位置上的值。则第 $i + 1$ 行、第 $j$ 列的值可以通过 $dp[j]$ + $dp[j - 1]$ 所得到。

需要注意：本题在计算的时候需要从右向左依次遍历每个元素位置，这是因为如果从左向右遍历，如果当前元素 $dp[j]$ 已经更新为当前阶段第 $j$ 列位置的状态值之后，右侧 $dp[j + 1]$ 想要更新的话，需要的是上一阶段的状态值 $dp[j]$，而此时 $dp[j]$ 已经更新了，会破坏当前阶段的状态值。而如果用从右向左的顺序，则不会出现该问题。

**描述**：给定一个非负整数 $rowIndex$。

**要求**：返回杨辉三角的第 $rowIndex$ 行。

因为这道题是从 $0$ 行开始计算，则可以先将 $rowIndex$ 加 $1$，计算出总共的行数，即 $numRows = rowIndex + 1$。

定义状态 $dp[i][j]$ 为：杨辉三角第 $i$ 行、第 $j$ 列位置上的值。

根据观察，很容易得出状态转移方程为：$dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]$，此时 $i > 0$，$j > 0$。

- 每一行第一列都为 $1$，即 $dp[i][0] = 1$。

- 每一行最后一列都为 $1$，即 $dp[i][i] = 1$。

根据题意和状态定义，将 $dp$ 最后一行返回。

因为 $dp[i][j]$ 仅依赖于上一行（第 $i - 1$ 行）的 $dp[i - 1][j - 1]$ 和 $dp[i - 1][j]$，所以我们没必要保存所有阶段的状态，只需要保存上一阶段的所有状态和当前阶段的所有状态就可以了，这样使用两个一维数组分别保存相邻两个阶段的所有状态就可以实现了。

定义 $dp[j]$ 为杨辉三角第 $i$ 行第 $j$ 列位置上的值。则第 $i + 1$ 行、第 $j$ 列的值可以通过 $dp[j]$ + $dp[j - 1]$ 所得到。

需要注意：本题在计算的时候需要从右向左依次遍历每个元素位置，这是因为如果从左向右遍历，如果当前元素 $dp[j]$ 已经更新为当前阶段第 $j$ 列位置的状态值之后，右侧 $dp[j + 1]$ 想要更新的话，需要的是上一阶段的状态值 $dp[j]$，而此时 $dp[j]$ 已经更新了，会破坏当前阶段的状态值。而是用从左向左的顺序，则不会出现该问题。

**描述**：给定一个代表三角形的二维数组 $triangle$，$triangle$ 共有 $n$ 行，其中第 $i$ 行（从 $0$ 开始编号）包含了 $i + 1$ 个数。

我们每一步只能从当前位置移动到下一行中相邻的节点上。也就是说，如果正位于第 $i$ 行第 $j$ 列的节点，那么下一步可以移动到第 $i + 1$ 行第 $j$ 列的位置上，或者第 $i + 1$ 行，第 $j + 1$ 列的位置上。

- 示例 2：

输入：triangle = [[-10]]

输出：-10

定义状态 $dp[i][j]$ 表示为：从顶部走到第 $i$ 行（从 $0$ 开始编号）、第 $j$ 列的位置时的最小路径和。

由于每一步只能从当前位置移动到下一行中相邻的节点上，想要移动到第 $i$ 行、第 $j$ 列的位置，那么上一步只能在第 $i - 1$ 行、第 $j - 1$ 列的位置上，或者在第 $i - 1$ 行、第 $j$ 列的位置上。则状态转移方程为：

$dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j]$。其中 $triangle[i][j]$ 表示第 $i$ 行、第 $j$ 列位置上的元素值。

在第 $0$ 行、第 $j$ 列时，最小路径和为 $triangle[0][0]$，即 $dp[0][0] = triangle[0][0]$。

根据我们之前定义的状态，$dp[i][j]$ 表示为：从顶部走到第 $i$ 行（从 $0$ 开始编号）、第 $j$ 列的位置时的最小路径和。为了计算出最小路径和，则需要再遍历一遍 $dp[size - 1]$ 行的每一列，求出最小值即为最终结果。

- **时间复杂度**：$O(C_n)$，其中 $n$ 为结果数组的大小，$C_n$ 是第 $n$ 个卡特兰数。

给定一个二维整数数组 envelopes 表示信封，其中 $envelopes[i] = [wi, hi]$，表示第 $i$ 个信封的宽度 $w_i$ 和高度 $h_i$。