使用简化的递归关系解决 Nth Catalan 问题

Question

最近在练习动态规划，遇到了nth-Catalan问题。在查看问题和加泰罗尼亚数字的公式后，我对如何动态编码解决方案感到困惑。我决定从数学上看这个问题并推导出公式：

(1) C_n = (4n - 2) / (n + 1) * C_{n - 1}

通过这样做，我很容易将它翻译成代码：

//Not sure if this solution is dynamic or not.
int ln = 1;
for(int i = 2; i <= n; i++){
    ln = ln * (4*i - 2) / (i + 1);
}
return ln;

在实施我的解决方案并检查之后，我查看了解决问题的动态方法。我很惊讶地看到它遵循从初始公式派生的递归公式：

(2) C_n = sum(n, i=0) (C_i * C_{n - i - 1})

这个程序运行的时间复杂度为 O(N^2)，而我的方法的复杂度为 O(N)。

上网查了一下，发现自己推导出的方程是简化的递推公式。然而，即使找到了多种编码解决方案，我也无法找到任何使用简化公式在 O(N) 时间内解决第 n 个加泰罗尼亚问题的解决方案。

我得到的最接近的是使用公式的 O(N) 方法：

(3) C_n = (2n choose n)/(n + 1)

在我找到的任何解决方案中都没有使用简化公式 (1) 是否有原因？