Java 中的 Dyck Path

在 Java 编程中，Dyck 路径是一种以特定方式探索网格的方法。考虑一个正方形网格，您希望在保持在对角线之上到达右上角。这里的想法是看看有多少种不同的路径可供您使用。

考虑一个 n × n 的正方形网格，左上角索引为 (0, 0)。Dyck 路径是连接左下角 (n-1, 0) 和右上角 (0, n-1) 的唯一行走路径。路径必须始终保持在从网格左下角到右下角的对角线之上。

这里的目标是确定并计算符合这些条件的 Dyck 路径的总数，即连接点 (n-1, 0) 到 (0, n-1) 的路径。

示例 1

输入： n = 1

输出 1

示例 2

输入： n = 4

输出 14

示例 3

输入： n = 6

输出 132

示例 4

输入： n = 8

输出 1430

方法：使用 Catalan 数

计算 Dyck 路径的方法基于 Catalan 数公式

C_n = (2n)! / [(n + 1)! * n!]

该公式表示长度为 2n 的 Dyck 路径的数量，该路径起源于点 (n-1, 0) 并结束于点 (0, n-1)。另一种表达方式是通过乘积

C_n = Π (n + k) / k, k 从 2 到 n

其中 n 是非负整数，k 的范围是从 2 到 n。该公式利用 Catalan 数的性质有效地计算了有效 Dyck 路径的数量。

算法

步骤 1： 从 main 方法开始。

步骤 2： 初始化一个整型变量 n，并设置为所需 Dyck 路径的长度。

步骤 3： 调用 countDyckPaths 方法，并将 n 作为参数传递。

步骤 4： 在 countDyckPaths 方法中

• 检查 n 是否小于 0。如果是，则返回 0，因为 Dyck 路径不能有负长度。
• 调用 calculateCatalanNumber 方法，并将 n 作为参数传递。
• 将计算出的 Catalan 数作为 Dyck 路径的数量返回。

步骤 5： 在 calculateCatalanNumber 方法中

• 确定 n 是否小于或等于 1。如果是，因为第 0 个和第 1 个 Catalan 数都为 1，所以返回 1。
• 初始化一个 Catalan 变量为 1。
• 使用循环，根据公式 Cn = (2n)! / ((n + 1)! * n!) 计算 Catalan 数的分子和分母部分。
  • 在每次迭代中，将 Catalan 乘以 (2 * n - i) 来计算分子。
  • 在每次迭代中，将 Catalan 除以 (i + 1) 来计算分母。
• 循环结束后，将 Catalan 除以 (n + 1) 得到 Cn 的最终值。
• 返回计算出的 Catalan 数。

步骤 6： 在 main 方法中打印获得的结果，表明指定长度的 Dyck 路径的数量。

实施

文件名： DyckPathsUsingCatalan.java

输出

Number of Dyck paths of length 4: 14

时间复杂度： 上述代码的时间复杂度为 O(n)，其中 n 是要计算 Dyck 路径数量的输入值。这是因为 calculateCatalanNumber 方法在 0 到 n 的范围内进行迭代，并在每次迭代中执行常数时间的操作。

辅助空间： 代码的辅助空间复杂度为 O(1)，这意味着它使用的额外空间量是恒定的，与输入值 n 无关。

方法：直接组合

直接组合方法（如提供的代码所示）在不显式生成数学结构（如 Catalan 数）的情况下进行计算。它直接使用组合公式计算所需结果，而无需遍历或生成结构的各个实例。

算法

步骤 1： 从 main 方法开始。

步骤 2： 初始化一个整型变量 length，并设置为所需 Dyck 路径的长度。

步骤 3： 调用 countDyckPaths 方法，并将 length 作为参数传递。

步骤 4： 在 countDyckPaths 方法中

1. 定义一个 numerator 变量，并通过调用 calculateFactorial 方法（参数为 2 * n）来计算它。
2. 声明一个 denominator 变量，并通过调用两次 calculateFactorial 方法（一次参数为 n + 1，一次参数为 n）相乘来计算其值。
3. 通过将 numerator 除以 denominator 来计算结果。
4. 将计算出的结果作为指定长度的 Dyck 路径的数量返回。

步骤 5： 在 calculateFactorial 方法中

1. 初始化一个整型变量 result 为 1。
2. 使用一个从 1 到输入数字的循环。
3. 在每次迭代中，将 result 乘以循环变量 i。
4. 返回 result 的最终值，即输入数字的阶乘。

步骤 6： 在 main 方法中打印获得的结果，表明指定长度的 Dyck 路径的数量。

实施

文件名： DyckPathCounter.java

输出

The number of Dyck paths with a length of 4 is: 14

时间复杂度： 提供的代码的时间复杂度为 O(n)，因为最耗时的操作是计算阶乘。通过一个从 1 到 'n' 迭代的循环来完成计算。由于循环的每次迭代都会增加成比例的工作量，因此总体时间复杂度会随着输入大小 'n' 线性增长，从而导致 O(n) 的时间复杂度。

辅助空间： 代码的辅助空间复杂度为 O(1)，因为它使用的额外内存量是固定的，与输入值 'n' 无关。numerator、denominator 和 result 等变量占用的空间量是恒定的，并且该分配不随 'n' 的大小而变化。因此，辅助空间复杂度不依赖于输入大小。